C# найти большие простые числа

Я пишу программу на C#, которая найдет все простые числа с максимальным размером UInt64, если только нет числовых данных, больших, чем UInt64. Я уже написал простую программу, но по какой-то причине она возвращает каждое число, которое я проверяю как простое, даже если оно не должно быть простым числом. Вот что у меня есть:C# найти большие простые числа

static void Main(string[] args) 
    { 
     UInt64 count = 0; 
     List<UInt64> primes = new List<UInt64>(); 
     bool prime = true; 

     do 
     { 
      for (UInt64 i = 2; i < count; i++) 
      { 
       if ((count % i) == 0) 
       { 
        prime = false; 
       } 
      } 

      if (prime == true) 
      { 
       primes.Add(count); 
       Console.WriteLine(count); 
      } 

      count++; 
      prime = true; 

     } while (count < UInt64.MaxValue); 
    }

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

источник

2013-12-07 Generalkidd

Вы должны рассмотреть возможность использования теста [primality test] (http://en.wikipedia.org/wiki/Primality_test), например [Sieve of Eratosthenes] (http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) - - он намного более эффективен, чем ваш алгоритм. – David

Этот алгоритм, возможно, может пропустить несколько простых чисел, когда вы достигнете очень высоких чисел, которые я намереваюсь сделать. Я хочу удостовериться, что смогу захватить все возможные простые числа, и единственный способ убедиться, что это проверка грубой силы на каждом отдельном номере. – Generalkidd

@ Generalkidd Я не вижу ошибку, но вы не получите очень высокие числа с помощью n-квадратного алгоритма, подобного этому. –

Я буквально скопировал ваш код в Visual Studio, запустил его, и он отлично работал. Алгоритм звучит, хотя вы определенно можете его оптимизировать.

источник

2013-12-07 08:14:28 Alec

Действительно, он отлично работает. –

Вы правы, я установил максимальное значение count равным 100, чтобы я мог видеть первые несколько наборов чисел. Я предполагаю, что когда у меня была программа, распечатав все штрихи, когда она их обнаружила, консоль была напечатана так быстро, что все выглядело так, как будто все, что она делало, печатало каждое число от 1 до предела (еще не достигнуто). – Generalkidd

Ну, в первую очередь, 0 и 1 не является простым и это очень медленный алгоритм. Вы должны рассмотреть некоторый optimaze код. Например this Но ваш код должен работать нормально.

источник

2013-12-07 08:44:12 PeterRing

Я запускаю эту программу в течение последнего часа или около того, я не уверен, где это сейчас, потому что я удаляю вывод консоли, но в диспетчере задач сама программа не использует большую мощность процессора. Фактически, он использует только около 28% от моей общей мощности процессора. В настоящее время я запускаю это на своем планшете Intel Atom Z2760. Почему программа не в полной мере использует все возможности процессора, чтобы идти быстрее? – Generalkidd

C# найти большие простые числа

ответ

Смежные вопросы