Каков наилучший способ найти самый большой простой коэффициент числа?

Question

Я новичок в программировании, и мой друг предложил мне сделать упражнение по проекту Эйлера, чтобы поправиться. Я столкнулся с проблемой по вопросу 3:

«Главными факторами 13195 являются 5, 7, 13 и 29. Какой самый большой простой коэффициент числа 600851475143?»

Теперь вот мое решение:

class Program 
{ 
    static void Main(string[] args) 
    { 
     long number = 600851475143; 
     bool prime = true; 

     for (long i = 3; i <= number; i++) 
     { 
      for (long n = 2; n < i; n++) 
      { 

       if (i % n == 0) 
       { 
        prime = false; 
        break; 
       } 
      } 

      if (prime) 
      { 
       if (number % i == 0) 
       { 
        Console.WriteLine(i); 

       } 

      } 
      prime = true; 

     } 
     Console.ReadKey(); 
    } 
} 

Теперь, когда я сделал получить правильный ответ (который 6857) Ive нашел мой метод очень неэффективен. Если вы запустите мой код, вы увидите, что он все равно будет работать после более чем двух минут ... Мой вопрос в том, как я могу написать более эффективный/быстрый код для этого?

Answer 1

Прежде всего алгоритм, который вы используете для того, чтобы узнать, является ли число простым или нет, очень неэффективен (порядок (n2)), вы можете улучшить порядок функции, возвращающей число премьер.

Чтобы определить, является ли число простым, вам нужно будет проверить, не делится ли он на любое число, меньшее n.

Вам нужно только учитывать коэффициенты до √n, потому что если n делится на некоторое число p, то n = p × q, а так как p ≤ q, вы можете получить, что p ≤ √n. Обратите внимание, что вы рассматриваете числовой коэффициент меньше n вместо менее √n.

Возможно, подобная проблема может помочь вам, «что является самым большим штрихом ниже».

Наилучший подход, чтобы решить эту проблему, используется Сито Эратосфена. (https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes)

Здесь находится псевдокод с использованием сита Эрастостфена.

public int primes(int n) { 
    boolean[] isPrime = new boolean[n]; 
    for (int i = 2; i < n; i++) { 
     isPrime[i] = true; 
    } 
    // Loop's ending condition is i * i < n instead of i < sqrt(n) 
    // to avoid repeatedly calling an expensive function sqrt(). 
    for (int i = 2; i * i < n; i++) { 
     if (!isPrime[i]) continue; 
     for (int j = i * i; j < n; j += i) { 
     isPrime[j] = false; 
     } 
    } 
    int count = 0; 
    for (int i = 2; i < n; i++) { 
     if (isPrime[i]) count++; 
    } 

    //return the max prime 
    int maxPrime = 1; 
    for(int i = 0; i < isPrime.count; i++){ 
     if(isPrime[i]){ 
     maxPrime = i; 
     } 
     return maxPrime; 
    } 
    } 

Answer 2

Если вы собираетесь работать над многими проблемами проекта Эйлера, то вы будете нуждаться в хорошей реализации решета Эратосфена. Два из полезных методов для вашего класса Eratosthenes: nextPrime(int p) и previousPrime(int p), который возвращает следующие и следующие младшие простые числа соответственно.

ETA: Псевдокод отредактирован как неправильный. Сожалею.

Answer 3

Я написал метод, который даст вам все основные факторы и самый большой из них. Мой код работает, вы можете просмотреть его:

public void PrimeFactor1(long n) 
{ 
    List<int> sList = new List<int>(); 
    long temp = 1; 
    for (int i = 2; i <= n; i++) 
    { 
     if ((n % i) == 0) 
     { 
      temp = n/i; 
      sList.Add(i); 
      i = 1; 
      n = temp; 
     }  
    } 
    string arr = string.Join(",", sList.ToArray()); 
    Console.Write(arr); 
    Console.WriteLine("."); 
    Console.WriteLine("The Biggest Prime number is: {0}", sList.Max()); 
} 

Answer 4

Мой вопрос, как я могу написать более эффективный/быстрый код для этого?

Это неправильный вопрос. Вернее, это преждевременный вопрос.

Правильные вопросы задавать являются:

• Является ли моя программа правильно?
• Является ли моя программа хорошо организованной?

Выполнение неправильной программы быстро дает вам возможность быстрее получать неправильные ответы, что не является улучшением. Сделать плохо организованную программу быстрее действительно сложно, так что сначала организуйте ее.

Давайте начнем с небольшого, но невероятно важного улучшения вашей программы: мы замечаем, что «эта вещь проста?» может быть четко представлена ​​хелпером:

class Program 
{ 
    static bool IsPrime(long i) 
    { 
    for (long n = 2; n < i; n++) 
    { 
     if (i % n == 0) 
     return false; 
    } 
    return true; 
    } 

    static void Main(string[] args) 
    { 
    long number = 600851475143; 
    for (long i = 3; i <= number; i++) 
    { 
     if (IsPrime(i)) 
     Console.WriteLine(i); 
    } 
    Console.ReadKey(); 
    } 
} 

Посмотрите, что именно там произошло. Ваша программа внезапно стала намного проще, понятнее. Что делает IsPrime? Он говорит вам, является ли целое число простым. Что делает основной цикл? Он печатает все простые числа между 3 и номером.

Теперь, начните сначала. Правильно ли каждая часть программы? № IsPrime возвращает true при заданном 1, но обычно это не считается простым. Исправить ошибку. Вы хотите, чтобы ваши вспомогательные методы были надежными. Убедитесь, что ваши вспомогательные методы делают именно то, что они говорят на олове. Напишите тесты! Поскольку вы хотите удостовериться, что, когда вы меняете эти методы, чтобы сделать их быстрее, вы не делаете их неправильными случайно.

Теперь, когда у нас есть правильные и хорошо организованные, мы можем начать оптимизацию. Можете ли вы придумать, как быстрее сделать IsPrime? Уверен:

• Нам нужно только проверить квадратный корень от i. (Обратите внимание, что n * n <= i быстрее, чем n <= Sqrt(i))
• После того, как мы проверили 2, мы не должны проверить 4, 6, 8, ...

Вы можете думать о других способов сделать это Быстрее?

Но ключ организует вашу программу хорошо. Когда у вас есть хорошо организованная программа, вы можете рассуждать на более высоком уровне, и вы можете найти и устранить медленные фигуры.