Самый эффективный код для первых 10000 простых чисел?
Я хочу напечатать первые 10000 простых чисел. Кто-нибудь может дать мне самый эффективный код для этого? Разъяснения:
- Не имеет значения, если ваш код неэффективен для n >10000.
- Размер кода не имеет значения.
- Вы не можете просто жестко закодировать значения любым способом.
31 ответ
Сито Аткина, вероятно, то, что вы ищете, его верхняя граница времени работы O(N/log log N).
Если вы используете только числа на 1 больше и на 1 меньше, чем кратные 6, это может быть даже быстрее, так как все простые числа выше 3 находятся на расстоянии 1 от кратного шести. Ресурс для моего выступления
Я рекомендую сито: сито Эратосфена или сито Аткина.
Сито или Eratosthenes, вероятно, наиболее интуитивный метод поиска списка простых чисел. В основном вы:
- Запишите список чисел от 2 до любого предела, скажем, 1000.
- Возьмите первое число, которое не вычеркнуто (для первой итерации это 2) и вычеркните все кратные этого числа из списка.
- Повторяйте шаг 2, пока не дойдете до конца списка. Все числа, которые не вычеркнуты, просты.
Очевидно, что для ускорения работы этого алгоритма можно сделать довольно много оптимизаций, но это основная идея.
Сито Аткина использует аналогичный подход, но, к сожалению, я не знаю достаточно об этом, чтобы объяснить это вам. Но я знаю, что алгоритм, который я связал, занимает 8 секунд, чтобы вычислить все простые числа до 1000000000 на древнем Pentium II-350
Сито Эратосфена Исходный код: http://web.archive.org/web/20140705111241/http://primes.utm.edu/links/programs/sieves/Eratosthenes/C_source_code/
Сито из исходного кода Atkin: http://cr.yp.to/primegen.html
Это не строго против ограничения жесткого кода, но очень близко. Почему бы не загрузить этот список программным способом и не распечатать его?
В Хаскеле мы можем почти дословно записать математическое определение сита Эратосфена: " простые числа - это натуральные числа выше 1 без каких-либо составных чисел, где композиты находятся путем перечисления кратных каждого простого числа ":
primes = 2 : minus [3..] (foldr (\p r -> p*p : union [p*p+p, p*p+2*p..] r)
[] primes)
primes !! 10000 почти мгновенно.
Рекомендации:
Приведенный выше код легко настраивается на работу только по коэффициентам, primes = 2 : 3 : minus [5,7..] (foldr (\p r -> p*p : union [p*p+2*p, p*p+4*p..] r) [] (tail primes)) , Сложность по времени значительно улучшается (примерно до логарифмического коэффициента выше оптимального) за счет сворачивания в древовидную структуру, а сложность пространства радикально улучшается при производстве многоступенчатых простых чисел, в
primes = 2 : _Y ( (3:) . sieve 5 . _U . map (\p -> [p*p, p*p+2*p..]) )
where
_Y g = g (_Y g) -- non-sharing fixpoint combinator
_U ((x:xs):t) = x : (union xs . _U . pairs) t -- ~= nub.sort.concat
pairs (xs:ys:t) = union xs ys : pairs t
sieve k s@(x:xs) | k < x = k : sieve (k+2) s -- ~= [k,k+2..]\\s,
| otherwise = sieve (k+2) xs -- when s⊂[k,k+2..]
(В Haskell круглые скобки используются для группировки, вызов функции обозначается просто сопоставлением, (:) является оператором минусов для списков, и (.) является оператором функциональной композиции: (f . g) x = (\y -> f (g y)) x = f (g x) ).
GateKiller, как насчет добавления break к этому if в foreach цикл? Это сильно ускорило бы ситуацию, потому что если 6 делится на 2, вам не нужно проверять 3 и 5. (Я бы все равно проголосовал за ваше решение, если бы у меня было достаточно репутации:-) ...)
ArrayList primeNumbers = new ArrayList();
for(int i = 2; primeNumbers.Count < 10000; i++) {
bool divisible = false;
foreach(int number in primeNumbers) {
if(i % number == 0) {
divisible = true;
break;
}
}
if(divisible == false) {
primeNumbers.Add(i);
Console.Write(i + " ");
}
}
@Matt: log(log(10000)) составляет ~2
Из статьи Википедии (которую вы цитировали) " Сито Аткина":
Это сито вычисляет простые числа до N, используя
O(N/log log N)операции только с N1/2 + o (1) битами памяти. Это немного лучше, чем сито Эратосфена, которое используетO(N)операций и O (N1/2(log log N) / log N) битов памяти (AOL Atkin, DJ Bernstein, 2004). Эти асимптотические вычислительные сложности включают в себя простые оптимизации, такие как разложение на множители, и разбиение вычислений на более мелкие блоки.
Учитывая асимптотические вычислительные сложности вдоль O(N) (для Эратосфена) и O(N/log(log(N))) (для Аткина) мы не можем сказать (для маленьких N=10_000) какой алгоритм, если он будет реализован, будет быстрее.
Ахим Фламменкамп написал в "Сите Эратосфена":
цитируется:
@ num1
Для интервалов, больших примерно 10^9, конечно, для тех, которые> 10^10, сито Эратосфена превосходит сито Аткинса и Бернштейна, которое использует неприводимые бинарные квадратичные формы. См. Их документ для справочной информации, а также параграф 5 доктора философии В. Голуэя. Тезис.
Поэтому для 10_000 Сито Эратосфена может быть быстрее, чем Сито Аткина.
Чтобы ответить на OP, код prime_sieve.c (цитируется num1)
Используя GMP, можно написать следующее:
#include <stdio.h>
#include <gmp.h>
int main() {
mpz_t prime;
mpz_init(prime);
mpz_set_ui(prime, 1);
int i;
char* num = malloc(4000);
for(i=0; i<10000; i++) {
mpz_nextprime(prime, prime);
printf("%s, ", mpz_get_str(NULL,10,prime));
}
}
На моем MacBook Pro с частотой 2,33 ГГц он работает следующим образом:
time ./a.out > /dev/null
real 0m0.033s
user 0m0.029s
sys 0m0.003s
Расчет 1 000 000 простых чисел на одном ноутбуке:
time ./a.out > /dev/null
real 0m14.824s
user 0m14.606s
sys 0m0.086s
GMP высоко оптимизирован для такого рода вещей. Если вы действительно не хотите понимать алгоритмы, написав свои собственные, вам будет рекомендовано использовать libGMP под C.
Совсем неэффективно, но вы можете использовать регулярное выражение для проверки простых чисел.
/^1?$|^(11+?)\1+$/
Это проверяет, если для строки, состоящей из k "1S, k не простое число (т. Е. Состоит ли строка из одного1Или любое число1Это можно выразить как n- ный продукт).
Я адаптировал код, найденный в CodeProject, для создания следующего:
ArrayList primeNumbers = new ArrayList();
for(int i = 2; primeNumbers.Count < 10000; i++) {
bool divisible = false;
foreach(int number in primeNumbers) {
if(i % number == 0) {
divisible = true;
}
}
if(divisible == false) {
primeNumbers.Add(i);
Console.Write(i + " ");
}
}
Тестирование этого на моем сервере ASP.NET заняло около 1 минуты для запуска.
Сито Эратосфена - это путь, благодаря своей простоте и скорости. Моя реализация в C
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
int main(void)
{
unsigned int lim, i, j;
printf("Find primes upto: ");
scanf("%d", &lim);
lim += 1;
bool *primes = calloc(lim, sizeof(bool));
unsigned int sqrtlim = sqrt(lim);
for (i = 2; i <= sqrtlim; i++)
if (!primes[i])
for (j = i * i; j < lim; j += i)
primes[j] = true;
printf("\nListing prime numbers between 2 and %d:\n\n", lim - 1);
for (i = 2; i < lim; i++)
if (!primes[i])
printf("%d\n", i);
return 0;
}
Время процессора, чтобы найти простые числа (на Pentium Dual Core E2140 1.6 ГГц, используя одноядерный)
~ 4 секунды для лимита = 100000000
Вот Сито Эратосфена, которое я написал в PowerShell несколько дней назад. У него есть параметр для определения количества простых чисел, которые должны быть возвращены.
#
# generate a list of primes up to a specific target using a sieve of eratosthenes
#
function getPrimes { #sieve of eratosthenes, http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
param ($target,$count = 0)
$sieveBound = [math]::ceiling(( $target - 1 ) / 2) #not storing evens so count is lower than $target
$sieve = @($false) * $sieveBound
$crossLimit = [math]::ceiling(( [math]::sqrt($target) - 1 ) / 2)
for ($i = 1; $i -le $crossLimit; $i ++) {
if ($sieve[$i] -eq $false) {
$prime = 2 * $i + 1
write-debug "Found: $prime"
for ($x = 2 * $i * ( $i + 1 ); $x -lt $sieveBound; $x += 2 * $i + 1) {
$sieve[$x] = $true
}
}
}
$primes = @(2)
for ($i = 1; $i -le $sieveBound; $i ++) {
if($count -gt 0 -and $primes.length -ge $count) {
break;
}
if($sieve[$i] -eq $false) {
$prime = 2 * $i + 1
write-debug "Output: $prime"
$primes += $prime
}
}
return $primes
}
Сито, кажется, неправильный ответ. Сито дает вам простые числа до числа N, а не первых N простых чисел. Запустите @Imran или @Andrew Szeto, и вы получите простые числа до N.
Сито может все еще использоваться, если вы продолжаете пробовать сита для все больших чисел, пока не достигнете определенного размера набора результатов, и используете некоторое кеширование уже полученных чисел, но я считаю, что оно все равно будет не быстрее, чем решение типа @Pat's,
Алгоритм ситового блеска, упомянутый Бен Голдбергом, заслуживает более пристального внимания не только потому, что он очень элегантный, но и потому, что иногда он может быть полезен на практике (в отличие от сита Аткина, которое является чисто академическим упражнением).
Основная идея алгоритма удаления сита состоит в том, чтобы использовать небольшое скользящее сито, которое является достаточно большим, чтобы содержать хотя бы одно отдельное кратное число для каждого из "активных" простых факторов в настоящее время - то есть тех простых чисел, квадрат которых не превышает наименьшее число В настоящее время представлено движущееся сито. Другое отличие от SoE состоит в том, что сито deque хранит фактические факторы в ячейках композитов, а не в логических значениях.
Алгоритм расширяет размер окна сита по мере необходимости, что приводит к достаточно равномерной производительности в широком диапазоне, пока сито не начнет заметно превышать емкость кэша L1 ЦП. Последнее простое число, которое подходит полностью, составляет 25 237 523 (1579 791-е простое число), что дает приблизительную приблизительную цифру для разумного рабочего диапазона алгоритма.
Алгоритм довольно прост и надежен, и его производительность даже в гораздо более широком диапазоне, чем у несегментированного сита Эратосфена. Последний работает намного быстрее, пока его сито полностью помещается в кэш, то есть до 2^16 для сита, рассчитанного только на шансы, с размерами в байтах. Затем его производительность падает все больше и больше, хотя он всегда остается значительно быстрее, чем deque, несмотря на помехи (по крайней мере, в скомпилированных языках, таких как C/C++, Pascal или Java/C#).
Вот рендеринг алгоритма deque sieve в C#, потому что я нахожу этот язык - несмотря на его многочисленные недостатки - гораздо более практичным для прототипирования алгоритмов и экспериментов, чем чрезвычайно громоздкий и педантичный C++. (Sidenote: я использую бесплатный LINQPad, который позволяет погружаться прямо, без всякой путаницы с настройкой проектов, make-файлов, каталогов или еще чего-то, и это дает мне ту же степень интерактивности, что и приглашение Python).
C# не имеет явного типа deque, но обычный List<int> работает достаточно хорошо для демонстрации алгоритма.
Примечание: эта версия не использует deque для простых чисел, потому что просто не имеет смысла выталкивать sqrt (n) из n простых чисел. Что хорошего в том, чтобы удалить 100 простых чисел и оставить 9900? По крайней мере, таким образом все простые числа собраны в аккуратный вектор, готовый для дальнейшей обработки.
static List<int> deque_sieve (int n = 10000)
{
Trace.Assert(n >= 3);
var primes = new List<int>() { 2, 3 };
var sieve = new List<int>() { 0, 0, 0 };
for (int sieve_base = 5, current_prime_index = 1, current_prime_squared = 9; ; )
{
int base_factor = sieve[0];
if (base_factor != 0)
{
// the sieve base has a non-trivial factor - put that factor back into circulation
mark_next_unmarked_multiple(sieve, base_factor);
}
else if (sieve_base < current_prime_squared) // no non-trivial factor -> found a non-composite
{
primes.Add(sieve_base);
if (primes.Count == n)
return primes;
}
else // sieve_base == current_prime_squared
{
// bring the current prime into circulation by injecting it into the sieve ...
mark_next_unmarked_multiple(sieve, primes[current_prime_index]);
// ... and elect a new current prime
current_prime_squared = square(primes[++current_prime_index]);
}
// slide the sieve one step forward
sieve.RemoveAt(0); sieve_base += 2;
}
}
Вот две вспомогательные функции:
static void mark_next_unmarked_multiple (List<int> sieve, int prime)
{
int i = prime, e = sieve.Count;
while (i < e && sieve[i] != 0)
i += prime;
for ( ; e <= i; ++e) // no List<>.Resize()...
sieve.Add(0);
sieve[i] = prime;
}
static int square (int n)
{
return n * n;
}
Вероятно, самый простой способ понять алгоритм - это представить его как специальное сегментированное сито Эратосфена с размером сегмента 1, сопровождаемое областью переполнения, где простые числа останавливаются, когда они пересекают конец сегмента. За исключением того, что единственная ячейка сегмента (иначе sieve[0]) уже просеян, когда мы доберемся до него, потому что он переехал, когда был частью области переполнения.
Число, которое представлено sieve[0] проводится в sieve_base, хотя sieve_front или же window_base также были бы хорошие имена, которые позволяют проводить параллели с кодом Бена или реализациями сегментированных / оконных сит.
Если sieve[0] содержит ненулевое значение, то это значение является фактором sieve_base, который, таким образом, может быть признан составным. Поскольку ячейка 0 кратна этому коэффициенту, легко вычислить ее следующий переход, который просто равен 0 плюс этот коэффициент. Если эта ячейка уже занята другим фактором, тогда мы просто добавляем фактор снова и так далее, пока не найдем множитель фактора, где в данный момент нет другого фактора (расширяя сито, если необходимо). Это также означает, что нет необходимости хранить текущие рабочие смещения различных простых чисел от одного сегмента к другому, как в обычном сегментированном сите. Всякий раз, когда мы находим фактор в sieve[0], его текущее рабочее смещение равно 0.
Текущее простое число вступает в игру следующим образом. Простое может стать текущим только после своего вхождения в поток (то есть, когда оно было обнаружено как простое, потому что не помечено каким-либо фактором), и оно будет оставаться текущим до того момента, когда sieve[0] достигает своей площади. Все более низкие кратные этого простого числа должны были быть исключены из-за действий меньших простых чисел, как в обычном SoE. Но ни одно из меньших простых чисел не может оторваться от квадрата, поскольку единственным фактором квадрата является само простое число, и на данный момент он еще не находится в обращении. Это объясняет действия, предпринятые алгоритмом по делу sieve_base == current_prime_squared (что подразумевает sieve[0] == 0, Кстати).
Теперь дело sieve[0] == 0 && sieve_base < current_prime_squared легко объяснимо: это означает, что sieve_base не может быть кратным ни одному из простых чисел, меньших, чем текущее простое число, иначе оно было бы помечено как составное. Я также не могу быть большим кратным текущего простого числа, поскольку его значение меньше квадрата текущего простого числа. Следовательно, это должно быть новое простое число.
Алгоритм, очевидно, основан на Сите Эратосфена, но в равной степени очевидно, что он сильно отличается. Сито Эратосфена получает превосходную скорость благодаря простоте своих элементарных операций: одно добавление индекса и одно хранилище для каждого шага операции - это все, что он делает в течение длительных периодов времени.
Вот простое несегментированное сито эратосфена, которое я обычно использую для просеивания простых чисел фактора в пределах короткого диапазона, т.е. до 2^16. Для этого поста я изменил его, чтобы он работал за пределами 2^16, подставив int за ushort
static List<int> small_odd_primes_up_to (int n)
{
var result = new List<int>();
if (n < 3)
return result;
int sqrt_n_halved = (int)(Math.Sqrt(n) - 1) >> 1, max_bit = (n - 1) >> 1;
var odd_composite = new bool[max_bit + 1];
for (int i = 3 >> 1; i <= sqrt_n_halved; ++i)
if (!odd_composite[i])
for (int p = (i << 1) + 1, j = p * p >> 1; j <= max_bit; j += p)
odd_composite[j] = true;
result.Add(3); // needs to be handled separately because of the mod 3 wheel
// read out the sieved primes
for (int i = 5 >> 1, d = 1; i <= max_bit; i += d, d ^= 3)
if (!odd_composite[i])
result.Add((i << 1) + 1);
return result;
}
При просеивании первых 10000 простых чисел будет превышен типичный кэш L1 объемом 32 КиБайта, но функция все еще очень быстра (доля миллисекунды даже в C#).
Если вы сравните этот код с ситом deque, то легко заметить, что операции сита deque намного сложнее, и он не может эффективно амортизировать свои накладные расходы, потому что он всегда делает кратчайшие возможные пересечения подряд (ровно одно вычеркивание после пропуска всех вычеркнутых кратных значений).
Примечание: код C# использует int вместо uint потому что новые компиляторы имеют привычку генерировать некачественный код для uint, вероятно, для того, чтобы подтолкнуть людей к целым числам со знаком... В приведенном выше варианте кода на C++ я использовал unsigned во всем, естественно; тест должен был быть в C++, потому что я хотел, чтобы он основывался на предположительно адекватном типе deque (std::deque<unsigned>; не было никакого увеличения производительности от использования unsigned short). Вот цифры для моего ноутбука Haswell (VC++ 2015/x64):
deque vs simple: 1.802 ms vs 0.182 ms
deque vs simple: 1.836 ms vs 0.170 ms
deque vs simple: 1.729 ms vs 0.173 ms
Примечание: время C# в два раза больше времени C++, что очень хорошо для C#, и это показывает, что List<int> не сутулится, даже если оскорблен как deque.
Простой ситовый код по-прежнему уносит пятно из воды, даже если он уже работает за пределами своего нормального рабочего диапазона (размер кэша L1 превышен на 50%, с перегрузкой кэша оператора). Доминирующая часть здесь - это считывание просеянных простых чисел, и это не сильно влияет на проблему с кешем. В любом случае функция была разработана для просеивания факторов факторов, то есть уровня 0 в трехуровневой иерархии сит, и обычно она должна возвращать только несколько сотен факторов или небольшое количество тысяч. Отсюда и его простота.
Производительность может быть улучшена более чем на порядок при использовании сегментированного сита и оптимизации кода для извлечения просеянных простых чисел (пошаговый мод 3 и развернутый дважды, или мод 15 и развернутый один раз), и, тем не менее, из-за большей производительности можно выжать из код с использованием колеса мод 16 или мод 30 со всеми обрезками (то есть полное развертывание для всех остатков). Нечто подобное объясняется в моем ответе Найти простое простое число в Code Review, где обсуждалась аналогичная проблема. Но трудно увидеть смысл в улучшении времени менее миллисекунды для одноразовой задачи...
Для краткости рассмотрим следующие моменты времени C++ для просеивания до 100 000 000:
deque vs simple: 1895.521 ms vs 432.763 ms
deque vs simple: 1847.594 ms vs 429.766 ms
deque vs simple: 1859.462 ms vs 430.625 ms
В отличие от этого, сегментированное сито в C# с несколькими наворотами выполняет ту же самую работу за 95 мс (нет доступных временных интервалов C++, поскольку в настоящее время я выполняю вызовы кода только в C#).
Ситуация может выглядеть совершенно иначе в интерпретируемом языке, таком как Python, где каждая операция сопряжена с большими затратами, и накладные расходы интерпретатора затмевают все различия из-за предсказанных или ошибочно предсказанных ветвлений или операций с подциклом (сдвиг, сложение) и операций с несколькими циклами (умножение) и, возможно, даже разделение). Это неизбежно подорвет преимущество простоты Решета Эратосфена, и это может сделать решение для настила немного более привлекательным.
Кроме того, во многих случаях, сообщаемых другими респондентами в этой теме, вероятно, преобладает время выхода. Это совершенно другая война, где моим главным оружием является простой класс, подобный этому:
class CCWriter
{
const int SPACE_RESERVE = 11; // UInt31 + '\n'
public static System.IO.Stream BaseStream;
static byte[] m_buffer = new byte[1 << 16]; // need 55k..60k for a maximum-size range
static int m_write_pos = 0;
public static long BytesWritten = 0; // for statistics
internal static ushort[] m_double_digit_lookup = create_double_digit_lookup();
internal static ushort[] create_double_digit_lookup ()
{
var lookup = new ushort[100];
for (int lo = 0; lo < 10; ++lo)
for (int hi = 0; hi < 10; ++hi)
lookup[hi * 10 + lo] = (ushort)(0x3030 + (hi << 8) + lo);
return lookup;
}
public static void Flush ()
{
if (BaseStream != null && m_write_pos > 0)
BaseStream.Write(m_buffer, 0, m_write_pos);
BytesWritten += m_write_pos;
m_write_pos = 0;
}
public static void WriteLine ()
{
if (m_buffer.Length - m_write_pos < 1)
Flush();
m_buffer[m_write_pos++] = (byte)'\n';
}
public static void WriteLinesSorted (int[] values, int count)
{
int digits = 1, max_value = 9;
for (int i = 0; i < count; ++i)
{
int x = values[i];
if (m_buffer.Length - m_write_pos < SPACE_RESERVE)
Flush();
while (x > max_value)
if (++digits < 10)
max_value = max_value * 10 + 9;
else
max_value = int.MaxValue;
int n = x, p = m_write_pos + digits, e = p + 1;
m_buffer[p] = (byte)'\n';
while (n >= 10)
{
int q = n / 100, w = m_double_digit_lookup[n - q * 100];
n = q;
m_buffer[--p] = (byte)w;
m_buffer[--p] = (byte)(w >> 8);
}
if (n != 0 || x == 0)
m_buffer[--p] = (byte)((byte)'0' + n);
m_write_pos = e;
}
}
}
Для записи 10000 (отсортированных) чисел требуется менее 1 мс. Это статический класс, потому что он предназначен для текстового включения в заявки на кодирование, с минимумом суеты и нулевых накладных расходов.
В общем, я обнаружил, что намного быстрее, если целенаправленная работа выполняется для целых пакетов, то есть просеивать определенный диапазон, затем извлекать все простые числа в вектор / массив, затем обрабатывать весь массив, затем просеивать следующий диапазон и так далее, вместо того, чтобы смешивать все вместе. Наличие отдельных функций, ориентированных на конкретные задачи, также облегчает их смешивание и сопоставление, позволяет повторно использовать и облегчает разработку / тестирование.
В питоне
import gmpy
p=1
for i in range(10000):
p=gmpy.next_prime(p)
print p
Адаптация и следование из GateKiller, вот последняя версия, которую я использовал.
public IEnumerable<long> PrimeNumbers(long number)
{
List<long> primes = new List<long>();
for (int i = 2; primes.Count < number; i++)
{
bool divisible = false;
foreach (int num in primes)
{
if (i % num == 0)
divisible = true;
if (num > Math.Sqrt(i))
break;
}
if (divisible == false)
primes.Add(i);
}
return primes;
}
Это в основном то же самое, но я добавил предложение "break on Sqrt" и изменил некоторые переменные, чтобы он лучше подходил для меня. (Я работал над Эйлером и мне нужно 10001-е простое число)
Вот мой код, который находит первые 10000 простых чисел за 0,049655 секунд на моем ноутбуке, первые 1000000 простых чисел менее чем за 6 секунд и первые 2 000 000 простых чисел за 15 секунд
Небольшое объяснение. Этот метод использует 2 метода, чтобы найти простое число
- во-первых, любое не простое число является составной из кратных простых чисел, так что этот тест кода путем деления номера теста на более простые простые числа вместо любого числа, это уменьшает вычисление по крайней мере в 10 раз для числа из 4 цифр и даже больше для большее число
- во-вторых, помимо деления на простое число, оно делит только на простые числа, которые меньше или равны корню проверяемого числа, что значительно сокращает вычисления, это работает, потому что любое число, большее чем корень числа, будет иметь номер аналога, который должно быть меньше, чем корень числа, но так как мы уже проверили все числа, меньшие, чем корень, поэтому нам не нужно беспокоиться о числе больше, чем корень проверяемого числа.
Пример вывода для первого 10000 простого числа
https://drive.google.com/open?id=0B2QYXBiLI-lZMUpCNFhZeUphck0 https://drive.google.com/open?id=0B2QYXBiLI-lZbmRtTkZETnp6Ykk
Вот код на языке C, введите 1, а затем 10 000, чтобы распечатать первые 10000 простых чисел.
Редактировать: я забыл, что это содержит библиотеку математики, если вы находитесь в Windows или Visual Studio, чем это должно быть хорошо, но в Linux вы должны скомпилировать код с помощью аргумента -lm, или код может не работать
Пример: gcc -Wall -o "%e" "%f" -lm
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <limits.h>
/* Finding prime numbers */
int main()
{
//pre-phase
char d,w;
int l,o;
printf(" 1. Find first n number of prime numbers or Find all prime numbers smaller than n ?\n"); // this question helps in setting the limits on m or n value i.e l or o
printf(" Enter 1 or 2 to get anwser of first or second question\n");
// decision making
do
{
printf(" -->");
scanf("%c",&d);
while ((w=getchar()) != '\n' && w != EOF);
if ( d == '1')
{
printf("\n 2. Enter the target no. of primes you will like to find from 3 to 2,000,000 range\n -->");
scanf("%10d",&l);
o=INT_MAX;
printf(" Here we go!\n\n");
break;
}
else if ( d == '2' )
{
printf("\n 2.Enter the limit under which to find prime numbers from 5 to 2,000,000 range\n -->");
scanf("%10d",&o);
l=o/log(o)*1.25;
printf(" Here we go!\n\n");
break;
}
else printf("\n Try again\n");
}while ( d != '1' || d != '2' );
clock_t start, end;
double cpu_time_used;
start = clock(); /* starting the clock for time keeping */
// main program starts here
int i,j,c,m,n; /* i ,j , c and m are all prime array 'p' variables and n is the number that is being tested */
int s,x;
int p[ l ]; /* p is the array for storing prime numbers and l sets the array size, l was initialized in pre-phase */
p[1]=2;
p[2]=3;
p[3]=5;
printf("%10dst:%10d\n%10dnd:%10d\n%10drd:%10d\n",1,p[1],2,p[2],3,p[3]); // first three prime are set
for ( i=4;i<=l;++i ) /* this loop sets all the prime numbers greater than 5 in the p array to 0 */
p[i]=0;
n=6; /* prime number testing begins with number 6 but this can lowered if you wish but you must remember to update other variables too */
s=sqrt(n); /* 's' does two things it stores the root value so that program does not have to calaculate it again and again and also it stores it in integer form instead of float*/
x=2; /* 'x' is the biggest prime number that is smaller or equal to root of the number 'n' being tested */
/* j ,x and c are related in this way, p[j] <= prime number x <= p[c] */
// the main loop begins here
for ( m=4,j=1,c=2; m<=l && n <= o;)
/* this condition checks if all the first 'l' numbers of primes are found or n does not exceed the set limit o */
{
// this will divide n by prime number in p[j] and tries to rule out non-primes
if ( n%p[j]==0 )
{
/* these steps execute if the number n is found to be non-prime */
++n; /* this increases n by 1 and therefore sets the next number 'n' to be tested */
s=sqrt(n); /* this calaulates and stores in 's' the new root of number 'n' */
if ( p[c] <= s && p[c] != x ) /* 'The Magic Setting' tests the next prime number candidate p[c] and if passed it updates the prime number x */
{
x=p[c];
++c;
}
j=1;
/* these steps sets the next number n to be tested and finds the next prime number x if possible for the new number 'n' and also resets j to 1 for the new cycle */
continue; /* and this restarts the loop for the new cycle */
}
// confirmation test for the prime number candidate n
else if ( n%p[j]!=0 && p[j]==x )
{
/* these steps execute if the number is found to be prime */
p[m]=n;
printf("%10dth:%10d\n",m,p[m]);
++n;
s = sqrt(n);
++m;
j=1;
/* these steps stores and prints the new prime number and moves the 'm' counter up and also sets the next number n to be tested and also resets j to 1 for the new cycle */
continue; /* and this restarts the loop */
/* the next number which will be a even and non-prime will trigger the magic setting in the next cycle and therfore we do not have to add another magic setting here*/
}
++j; /* increases p[j] to next prime number in the array for the next cycle testing of the number 'n' */
// if the cycle reaches this point that means the number 'n' was neither divisible by p[j] nor was it a prime number
// and therfore it will test the same number 'n' again in the next cycle with a bigger prime number
}
// the loops ends
printf(" All done !!\n");
end = clock();
cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
printf(" Time taken : %lf sec\n",cpu_time_used);
}
Вот мой код VB 2008, который находит все простые числа <10000000 за 1 минуту 27 секунд на моем рабочем ноутбуке. Он пропускает четные числа и ищет только простые числа, которые являются <квадратом тестового числа. Он предназначен только для поиска простых чисел от 0 до значения часового.
Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles
Button1.Click
Dim TestNum As Integer
Dim X As Integer
Dim Z As Integer
Dim TM As Single
Dim TS As Single
Dim TMS As Single
Dim UnPrime As Boolean
Dim Sentinal As Integer
Button1.Text = "Thinking"
Button1.Refresh()
Sentinal = Val(SentinalTxt.Text)
UnPrime = True
Primes(0) = 2
Primes(1) = 3
Z = 1
TM = TimeOfDay.Minute
TS = TimeOfDay.Second
TMS = TimeOfDay.Millisecond
For TestNum = 5 To Sentinal Step 2
Do While Primes(X) <> 0 And UnPrime And Primes(X) ^ 2 <= TestNum
If Int(TestNum / Primes(X)) - (TestNum / Primes(X)) = 0 Then
UnPrime = False
End If
X = X + 1
Loop
If UnPrime = True Then
X = X + 1
Z = Z + 1
Primes(Z) = TestNum
End If
UnPrime = True
X = 0
Next
Button1.Text = "Finished with " & Z
TM = TimeOfDay.Minute - TM
TS = TimeOfDay.Second - TS
TMS = TimeOfDay.Millisecond - TMS
ShowTime.Text = TM & ":" & TS & ":" & TMS
End Sub
Следующий код Mathcad вычисляет первый миллион простых чисел менее чем за 3 минуты.
Имейте в виду, что это будет использовать двойные числа с плавающей точкой для всех чисел и в основном интерпретируется. Надеюсь, синтаксис понятен.
Используя Сито Эратосфена, вычисления выполняются намного быстрее по сравнению с "общеизвестным" алгоритмом простых чисел.
Используя псевдокод из его вики ( https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes), я смогу найти решение для C#.
/// Get non-negative prime numbers until n using Sieve of Eratosthenes.
public int[] GetPrimes(int n) {
if (n <= 1) {
return new int[] { };
}
var mark = new bool[n];
for(var i = 2; i < n; i++) {
mark[i] = true;
}
for (var i = 2; i < Math.Sqrt(n); i++) {
if (mark[i]) {
for (var j = (i * i); j < n; j += i) {
mark[j] = false;
}
}
}
var primes = new List<int>();
for(var i = 3; i < n; i++) {
if (mark[i]) {
primes.Add(i);
}
}
return primes.ToArray();
}
GetPrimes (100000000) занимает 2 с и 330 мс.
ПРИМЕЧАНИЕ. Значение может отличаться в зависимости от технических характеристик оборудования.
Вот решение C++, использующее форму SoE:
#include <iostream>
#include <deque>
typedef std::deque<int> mydeque;
void my_insert( mydeque & factors, int factor ) {
int where = factor, count = factors.size();
while( where < count && factors[where] ) where += factor;
if( where >= count ) factors.resize( where + 1 );
factors[ where ] = factor;
}
int main() {
mydeque primes;
mydeque factors;
int a_prime = 3, a_square_prime = 9, maybe_prime = 3;
int cnt = 2;
factors.resize(3);
std::cout << "2 3 ";
while( cnt < 10000 ) {
int factor = factors.front();
maybe_prime += 2;
if( factor ) {
my_insert( factors, factor );
} else if( maybe_prime < a_square_prime ) {
std::cout << maybe_prime << " ";
primes.push_back( maybe_prime );
++cnt;
} else {
my_insert( factors, a_prime );
a_prime = primes.front();
primes.pop_front();
a_square_prime = a_prime * a_prime;
}
factors.pop_front();
}
std::cout << std::endl;
return 0;
}
Обратите внимание, что эта версия сита может вычислять простые числа бесконечно.
Также обратите внимание, STL deque принимает O(1) время выполнять push_back, pop_front и произвольный доступ через подписку.
resize операция занимает O(n) время, где n количество добавляемых элементов. Из-за того, как мы используем эту функцию, мы можем рассматривать эту небольшую константу.
Тело while зациклиться my_insert выполняется O(log log n) раз, где n равно переменной maybe_prime, Это потому, что выражение условия while будет оцениваться как истина один раз для каждого простого фактора maybe_prime, Смотрите " Функция делителя " в Википедии.
Умножение на количество раз my_insert называется, показывает, что это должно занять O(n log log n) время перечислять n простые числа... что неудивительно, что временная сложность, которая должна иметь Сито Эратосфена.
Однако, хотя этот код эффективен, он не самый эффективный... Я бы настоятельно рекомендовал использовать специализированную библиотеку для генерации простых чисел, например, простых чисел. Любое по-настоящему эффективное, хорошо оптимизированное решение потребует больше кода, чем кто-либо хочет ввести в Stackru.
Вот код, который я сделал:
enter code here
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT*/
unsigned long int n;
int prime(unsigned long int);
scanf("%ld",&n);
unsigned long int val;
for(unsigned long int i=0;i<n;i++)
{
int flag=0;
scanf("%ld",&val);
flag=prime(val);
if(flag==1)
printf("yes\n");
else
printf("no\n");
}
return 0;
}
int prime(unsigned long int n)
{
if(n==2) return 1;
else if (n == 1||n%2==0) return 0;
for (unsigned long int i=3; i<=sqrt(n); i+=2)
if (n%i == 0)
return 0;
return 1;
}
def compute_primes(bound):
"""
Return a list of the prime numbers in range(2, bound)
Implement the Sieve of Eratosthenes
https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
"""
primeNumber = [True for i in range(bound + 1)]
start_prime_number = 2
primes = []
while start_prime_number * start_prime_number <=bound:
# If primeNumber[start_prime_number] is not changed, then it is a prime
if primeNumber[start_prime_number]:
# Update all multiples of start_prime_number
for i in range(start_prime_number * start_prime_number, bound + 1, start_prime_number):
primeNumber[i] = False
start_prime_number += 1
# Print all prime numbers
for start_prime_number in range(2, bound + 1):
if primeNumber[start_prime_number]:
primes.append(start_prime_number)
return primes
печать (len(compute_primes(200)))
печать (len(compute_primes(2000)))
Я могу дать вам несколько советов, вы должны реализовать это.
- За каждое число получите половину этого числа. Например, для проверки 21, только получить остаток, разделив его от диапазона 2-10.
- Если это нечетное число, делите только на нечетное число, и наоборот. Например, для 21, разделите только на 3, 5, 7, 9.
Самый эффективный метод, который я получил до сих пор.
Использование метода Array.prototype.find() в Javascript. 2214,486 мс
function isPrime (number) {
function prime(element) {
let start = 2;
while (start <= Math.sqrt(element)) {
if (element % start++ < 1) {
return false;
}
}
return element > 1;
}
return [number].find(prime)
}
function logPrimes (n) {
let count = 0
let nth = n
let i = 0
while (count < nth) {
if (isPrime(i)) {
count++
console.log('i', i) //NOTE: If this line is ommited time to find 10,000th prime is 121.157ms
if (count === nth) {
console.log('while i', i)
console.log('count', count)
}
}
i++
}
}
console.time(logPrimes)
logPrimes(10000)
console.timeEnd(logPrimes) // 2214.486ms
Это старый вопрос, но здесь что-то не хватает...
Для простых чисел этот маленький, суд разделение не является, что медленно... Есть только 25 простых чисел под 100. С таким малым количеством простых чисел в тесте, и такие маленькие штрихи, мы можем вытащить аккуратный трюк!
Если a взаимно просто с b, то gcd a b = 1. Взаимно прост. Веселое слово. Означает, что в нем нет основных факторов. Таким образом, мы можем проверить делимость на несколько простых чисел с помощью одного вызова GCD. Как много? Итак, произведение первых 15 простых чисел меньше 2^64. И произведение следующих 10 также меньше 2^64. Это все 25, что нам нужно. Но стоит ли оно того?
Давайте посмотрим:
check x = null $ filter ((==0) . (x `mod`)) $ [<primes up to 101>]
Prelude> length $ filter check [101,103..85600]
>>> 9975
(0.30 secs, 125,865,152 bytes
a = 16294579238595022365 :: Word64
b = 14290787196698157718
pre = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
primes = (pre ++) $ filter ((==1) . gcd a) $ filter ((==1) . gcd b) [99,101..85600]
main = print $ length primes
Prelude> main
>>> 10000
(0.05 secs, 36,387,520 bytes)
Это шестикратное улучшение.
(lengthэто заставить список быть вычисленным. По умолчанию Haskell печатает по одному символу Unicode за раз, поэтому фактическая печать списка будет либо доминировать во времени, либо преобладать над количеством фактически используемого кода.)
Конечно, это работает в GHCi - реплицируемом интерпретируемом коде - на старом ноутбуке, и он не интерпретирует ни одно из этих чисел как int64s или даже BigInts, и не будет, даже если вы попросите его (ну, вы можете заставить его, но это некрасиво и действительно не помогает). Он интерпретирует каждое отдельное число там как обобщенные целочисленные вещи, которые можно специализировать для определенного типа с помощью поиска по словарю, и он просматривает связанный список (который здесь не объединен, поскольку он не компилируется) 3 раза. Интересно, что ручное объединение двух фильтров фактически замедляет его в REPL.
Скомпилируем:
...\Haskell\8.6\Testbed>Primes.exe +RTS -s
10000
606,280 bytes allocated in the heap
Total time 0.000s ( 0.004s elapsed)
Используя отчет RTS, поскольку Windows. Некоторые строки обрезаны, потому что они не актуальны - это были другие данные GC или измерения только части выполнения, и вместе они составляют 0,004 секунды (или меньше). Это также не постоянное сворачивание, потому что Haskell на самом деле этого не делает. Если мы постоянно фолдим (main = print 10000), мы получаем значительно меньшее выделение:
...Haskell\8.6\Testbed>Primes.exe +RTS -s
10000
47,688 bytes allocated in the heap
Total time 0.000s ( 0.001s elapsed)
Буквально достаточно, чтобы загрузить среду выполнения, а затем обнаружить, что ничего не остается, кроме как вывести число и выйти. Добавим факторизацию колеса:
wheel = scanl (+) 7 $ cycle [4, 2, 4, 2, 4, 6, 2, 6]
primes = (pre ++) $ filter ((==1) . gcd a) $ filter ((==1) . gcd b) $ takeWhile (<85600) wheel
Total time 0.000s ( 0.003s elapsed)
Уменьшено примерно на 1/3 по сравнению с нашей ссылкой на main = print 10000, но определенно есть место для дополнительной оптимизации. Например, он фактически остановился, чтобы выполнить сборку мусора, тогда как при настройке не должно быть никакого использования кучи. По какой-то причине компиляция для профилирования здесь фактически сокращает время выполнения до 2 миллисекунд:
Tue Nov 12 21:13 2019 Time and Allocation Profiling Report (Final)
Primes.exe +RTS -p -RTS
total time = 0.00 secs (2 ticks @ 1000 us, 1 processor)
total alloc = 967,120 bytes (excludes profiling overheads)
Я собираюсь оставить это как есть, я почти уверен, что случайный джиттер начинает преобладать.
Я работал над поиском простых чисел около года. Вот что я нашел самым быстрым:
import static java.lang.Math.sqrt;
import java.io.PrintWriter;
import java.io.File;
public class finder {
public static void main(String[] args) {
primelist primes = new primelist();
primes.insert(3);
primes.insert(5);
File file = new File("C:/Users/Richard/Desktop/directory/file0024.txt");
file.getParentFile().mkdirs();
long time = System.nanoTime();
try{
PrintWriter printWriter = new PrintWriter ("file0024.txt");
int linenum = 0;
printWriter.print("2");
printWriter.print (" , ");
printWriter.print("3");
printWriter.print (" , ");
int up;
int down;
for(int i =1; i<357913941;i++){//
if(linenum%10000==0){
printWriter.println ("");
linenum++;
}
down = i*6-1;
if(primes.check(down)){
primes.insert(down);
//System.out.println(i*6-1);
printWriter.print ( down );
printWriter.print (" , ");
linenum++;
}
up = i*6+1;
if(primes.check(up)){
primes.insert(up);
//System.out.println(i*6+1);
printWriter.print ( up );
printWriter.print (" , ");
linenum++;
}
}
printWriter.println ("Time to execute");
printWriter.println (System.nanoTime()-time);
//System.out.println(primes.length);
printWriter.close ();
}catch(Exception e){}
}
}
class node{
node next;
int x;
public node (){
node next;
x = 3;
}
public node(int z) {
node next;
x = z;
}
}
class primelist{
node first;
int length =0;
node current;
public void insert(int x){
node y = new node(x);
if(current == null){
current = y;
first = y;
}else{
current.next = y;
current = y;
}
length++;
}
public boolean check(int x){
int p = (int)sqrt(x);
node y = first;
for(int i = 0;i<length;i++){
if(y.x>p){
return true;
}else if(x%y.x ==0){
return false;
}
y = y.next;
}
return true;
}
}
1902465190909 нано секунд, чтобы добраться до 2147483629, начиная с 2.
Я написал это с использованием Python, так как я только начал изучать его, и он прекрасно работает. Десятый тысячный штрих генерируется этим кодом, как указано в http://primes.utm.edu/lists/small/10000.txt. Чтобы проверить, если n простое или нет, разделить n по номерам из 2 в sqrt(n), Если какой-либо из этого диапазона числа идеально делится n тогда это не главное.
import math
print ("You want prime till which number??")
a = input()
a = int(a)
x = 0
x = int(x)
count = 1
print("2 is prime number")
for c in range(3,a+1):
b = math.sqrt(c)
b = int(b)
x = 0
for b in range(2,b+1):
e = c % b
e = int(e)
if (e == 0):
x = x+1
if (x == 0):
print("%d is prime number" % c)
count = count + 1
print("Total number of prime till %d is %d" % (a,count))
Поскольку вы хотите только первые 10000 простых чисел, а не кодировать сложный алгоритм, я предложу следующее
boolean isPrime(int n){
//even but is prime
if(n==2)
return true;
//even numbers filtered already
if(n==0 || n==1 || n%2==0)
return false;
// loop for checking only odd factors
// i*i <= n (same as i<=sqrt(n), avoiding floating point calculations)
for(int i=3 ; i*i <=n ; i+=2){
// if any odd factor divides n then its not a prime!
if(n%i==0)
return false;
}
// its prime now
return true;
}
Теперь вызов прост, как вам нужно
for(int i=1 ; i<=1000 ; i++){
if(isPrime(i)){
//do something
}
}
Это код Python, который печатает простые числа от 1 до 1000000.
import math
k=0
factor=0
pl=[]
for i in range(1,1000000):
k=int(math.sqrt(i))
if i==2 or i==3:
pl.append(i)
for j in range(2,k+1):
if i%j==0:
factor=factor+1
elif factor==0 and j==k:
pl.append(i)
factor=0
print(pl)
print(len(pl))
Я трачу некоторое время на написание программы, вычисляющей много простых чисел, и этот код я использую для вычисления текстового файла, содержащего первые 1.000.000.000 простых чисел. Это на немецком языке, но интересная часть метода calcPrimes(), Простые числа хранятся в массиве под названием Primzahlen. Я рекомендую 64-битный процессор, потому что вычисления с 64-битными целыми числами.
import java.io.*;
class Primzahlengenerator {
long[] Primzahlen;
int LastUnknown = 2;
public static void main(String[] args) {
Primzahlengenerator Generator = new Primzahlengenerator();
switch(args.length) {
case 0: //Wenn keine Argumente übergeben worden:
Generator.printHelp(); //Hilfe ausgeben
return; //Durchfallen verhindern
case 1:
try {
Generator.Primzahlen = new long[Integer.decode(args[0]).intValue()];
}
catch (NumberFormatException e) {
System.out.println("Das erste Argument muss eine Zahl sein, und nicht als Wort z.B. \"Tausend\", sondern in Ziffern z.B. \"1000\" ausgedrückt werden.");//Hinweis, wie man die Argumente angeben muss ausgeben
Generator.printHelp(); //Generelle Hilfe ausgeben
return;
}
break;//dutchfallen verhindern
case 2:
switch (args[1]) {
case "-l":
System.out.println("Sie müsen auch eine Datei angeben!"); //Hilfemitteilung ausgeben
Generator.printHelp(); //Generelle Hilfe ausgeben
return;
}
break;//durchfallen verhindern
case 3:
try {
Generator.Primzahlen = new long[Integer.decode(args[0]).intValue()];
}
catch (NumberFormatException e) {
System.out.println("Das erste Argument muss eine Zahl sein, und nicht als Wort z.B. \"Tausend\", sondern in Ziffern z.B. \"1000\" ausgedrückt werden.");//Hinweis, wie man die Argumente angeben muss ausgeben
Generator.printHelp(); //Generelle Hilfe ausgeben
return;
}
switch(args[1]) {
case "-l":
Generator.loadFromFile(args[2]);//Datei Namens des Inhalts von Argument 3 lesen, falls Argument 2 = "-l" ist
break;
default:
Generator.printHelp();
break;
}
break;
default:
Generator.printHelp();
return;
}
Generator.calcPrims();
}
void printHelp() {
System.out.println("Sie müssen als erstes Argument angeben, die wieviel ersten Primzahlen sie berechnen wollen."); //Anleitung wie man das Programm mit Argumenten füttern muss
System.out.println("Als zweites Argument können sie \"-l\" wählen, worauf die Datei, aus der die Primzahlen geladen werden sollen,");
System.out.println("folgen muss. Sie muss genauso aufgebaut sein, wie eine Datei Primzahlen.txt, die durch den Aufruf \"java Primzahlengenerator 1000 > Primzahlen.txt\" entsteht.");
}
void loadFromFile(String File) {
// System.out.println("Lese Datei namens: \"" + File + "\"");
try{
int x = 0;
BufferedReader in = new BufferedReader(new FileReader(File));
String line;
while((line = in.readLine()) != null) {
Primzahlen[x] = new Long(line).longValue();
x++;
}
LastUnknown = x;
} catch(FileNotFoundException ex) {
System.out.println("Die angegebene Datei existiert nicht. Bitte geben sie eine existierende Datei an.");
} catch(IOException ex) {
System.err.println(ex);
} catch(ArrayIndexOutOfBoundsException ex) {
System.out.println("Die Datei enthält mehr Primzahlen als der reservierte Speicherbereich aufnehmen kann. Bitte geben sie als erstes Argument eine größere Zahl an,");
System.out.println("damit alle in der Datei enthaltenen Primzahlen aufgenommen werden können.");
}
/* for(long prim : Primzahlen) {
System.out.println("" + prim);
} */
//Hier soll code stehen, der von der Datei mit angegebenem Namen ( Wie diese aussieht einfach durch angeben von folgendem in cmd rausfinden:
//java Primzahlengenerator 1000 > 1000Primzahlen.txt
//da kommt ne textdatei, die die primzahlen enthält. mit Long.decode(String ziffern).longValue();
//erhält man das was an der entsprechenden stelle in das array soll. die erste zeile soll in [0] , die zweite zeile in [1] und so weiter.
//falls im arry der platz aus geht(die exception kenn ich grad nich, aber mach mal:
//int[] foo = { 1, 2, 3};
//int bar = foo[4];
//dann kriegst ne exception, das ist die gleiche die man kriegt, wenn im arry der platzt aus geht.
}
void calcPrims() {
int PrimzahlNummer = LastUnknown;
// System.out.println("LAstUnknown ist: " + LastUnknown);
Primzahlen[0] = 2;
Primzahlen[1] = 3;
long AktuelleZahl = Primzahlen[PrimzahlNummer - 1];
boolean IstPrimzahl;
// System.out.println("2");
// System.out.println("3");
int Limit = Primzahlen.length;
while(PrimzahlNummer < Limit) {
IstPrimzahl = true;
double WurzelDerAktuellenZahl = java.lang.Math.sqrt(AktuelleZahl);
for(int i = 1;i < PrimzahlNummer;i++) {
if(AktuelleZahl % Primzahlen[i] == 0) {
IstPrimzahl = false;
break;
}
if(Primzahlen[i] > WurzelDerAktuellenZahl) break;
}
if(IstPrimzahl) {
Primzahlen[PrimzahlNummer] = AktuelleZahl;
PrimzahlNummer++;
// System.out.println("" + AktuelleZahl);
}
AktuelleZahl = AktuelleZahl + 2;
}
for(long prim : Primzahlen) {
System.out.println("" + prim);
}
}
}