Я хочу напечатать первые 10000 простых чисел. Кто-нибудь может дать мне наиболее эффективный код для этого? Разъяснения:
- Не имеет значения, если ваш код неэффективен для n> 10000.
- Размер кода не имеет значения.
- Вы не можете просто жестко закодировать значения любым способом.
Сито Аткина , вероятно, то, что вы ищете, его верхняя граница времени работы 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
n
. Это не строго против ограничения жесткого кода, но очень близко. Почему бы не загрузить этот список программным способом и не распечатать его?
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 + " ");
}
}
В Хаскеле мы можем почти дословно записать математическое определение сита Эратосфена: « простые числа - это натуральные числа выше 1 без каких-либо составных чисел, где композиты находятся путем перечисления кратных каждого простого числа »:
import Data.List.Ordered (minus, union)
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 круглые скобки используются для группировки, вызов функции обозначается просто сопоставлением, (:)
является оператором cons для списков и (.)
оператором функциональной композиции:) (f . g) x = (\y -> f (g y)) x = f (g x)
.
@Matt: log (log (10000)) составляет ~ 2
Из статьи википедии (которую вы цитировали) « Сито Аткина» :
Это сито вычисляет простые числа до N, используя
O(N/log log N)
операции только с N 1/2 + o (1) битами памяти. Это немного лучше, чем сито Эратосфена, которое используетO(N)
операции и O (N 1/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.
mpz_nextprime
вычисляет простые числа по одному, а не все сразу с ситомСовсем неэффективно, но вы можете использовать регулярное выражение для проверки простых чисел.
/^1?$|^(11+?)\1+$/
Это проверяет, если для строки, состоящей из k « 1
» s, 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 минуты для запуска.
divisible = true
, путем обработки только нечетных чисел, превышающих 2, и с помощью любого из нескольких других методов, в том числе упомянутого @Clayton. Конечно, не самый эффективный. Вот Сито Эратосфена, которое я написал в 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
}
Сито Эратосфена - это путь, благодаря своей простоте и скорости. Моя реализация в 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 секунды для лимита = 100 000 000
primes
вводит в заблуждение, в вашем коде его значение is_composite_number
. Вы можете исключить первый цикл, если замените malloc
на calloc
. Выражение j+=i
может переполниться для большого lim
(и вы пропустите некоторые простые числа в этом случае). calloc
и альтернативное имя массива. Я также думал, что простые числа [] довольно запутанные, но не мог придумать лучшего названия. calloc
теперь, получим lim = 100 000 000 за ~ 4 сАдаптация и последующая работа с 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-е простое число)
Сито, кажется, неправильный ответ. Сито дает вам простые числа до числа N , а не первых N простых чисел. Запустите @Imran или @Andrew Szeto, и вы получите простые числа до N.
Сито может все еще использоваться, если вы продолжаете пробовать сита для все больших чисел, пока не достигнете определенного размера набора результатов, и используете некоторое кэширование уже полученных чисел, но я считаю, что оно все равно будет не быстрее, чем решение типа @ Pat's ,
m = n(log n + log (log n))
, например , n>= 6
(см. Википедию ). Кроме того, сито Эратосфена может быть переформулировано как сегментированное, что делает его действительно добавочным. В питоне
import gmpy
p=1
for i in range(10000):
p=gmpy.next_prime(p)
print p
Deque решета алгоритма упомянутого BenGoldberg заслуживает более подробного рассмотрения, не только потому , что это очень элегантно , но и потому , что иногда может быть полезны на практике ( в отличии от Решета Аткина, который является чисто академическим упражнением).
Основная идея алгоритма удаления сита состоит в том, чтобы использовать небольшое скользящее сито, которое является достаточно большим, чтобы содержать хотя бы одно отдельное кратное число для каждого из «активных» простых факторов в настоящее время - то есть тех простых чисел, квадрат которых не превышает наименьшее число В настоящее время представлено движущееся сито. Другое отличие от 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, сопровождаемое областью переполнения, где простые числа останавливаются при прохождении через конец сегмента. За исключением того, что единственная ячейка сегмента (aka 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;
}
}
}
Это занимает менее 1 мс для записи 10000 (отсортированных) чисел. Это статический класс, потому что он предназначен для текстового включения в заявки на кодирование, с минимумом суеты и нулевых накладных расходов.
В общем, я обнаружил, что намного быстрее, если целенаправленная работа выполняется для целых пакетов, то есть просеять определенный диапазон, затем извлечь все простые числа в вектор / массив, затем взорвать весь массив, затем просеять следующий диапазон и так далее, вместо того, чтобы смешивать все вместе. Наличие отдельных функций, ориентированных на конкретные задачи, также облегчает их смешивание и сопоставление, позволяет повторно использовать и облегчает разработку / тестирование.
factors.resize(3)
затем int factor = factors.front();
... не вижу ничего положенного в deque, так что он из этого выходит? ...). Придется изучить ваш код, надеюсь, он будет понятнее и понятнее. resize(3)
в пустой деке или векторе его инициализация равна трем нулям, как это делает мой код с инициализатором { 0, 0, 0 }
. Самый простой способ попасть в алгоритм - это мысленное символическое выполнение в течение нескольких итераций или загрузка его в LINQPad и отладка (то есть наблюдение за его работой). Надеюсь, мой код должен сделать это немного проще, чем у Бена ... Кроме того: хранение фактора в данном слоте не только помечает слот как составной (то есть кратный этому фактору); это также единственное место, где хранится этот фактор, и это неявное «рабочее смещение» фактора. 2 : fix ( (3:) . minus [5,7..] . unionAll . map (\p-> [p*p, p*p+2*p..]) )
( с использованием Data.List.Ordered
модуля «s minus
и unionAll
т) с Хаскеллой лень держать его„местный“. Опять же, не слишком производительный , но освещающий. :) Еще раз спасибо за указатели. Вот мой код VB 2008, который находит все простые числа <10 000 000 за 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 минуты.
Имейте в виду, что это будет использовать двойные числа с плавающей запятой для всех чисел и в основном интерпретируется. Надеюсь, синтаксис понятен.
Вот решение 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
цикла in my_insert
выполняется O(log log n)
раз, где n
равно переменной maybe_prime
. Это потому, что выражение условия while
будет иметь значение true один раз для каждого простого множителя maybe_prime
. Смотрите " Функция делителя " в Википедии.
Умножение на количество раз, которое my_insert
вызывается, показывает, что O(n log log n)
для составления списка n
простых чисел требуется время ... что неудивительно, что временная сложность, которую должен иметь Сито Эратосфена.
Однако, в то время как этот код является эффективным, это не самым эффективным ... Я бы настоятельно рекомендую использовать специализированную библиотеку для генерации простых чисел, таких как primesieve . Любое действительно эффективное, хорошо оптимизированное решение потребует больше кода, чем кто-либо хочет ввести в Stackoverflow.
tail(cycle (1:replicate(p-1)0))
. Вместо одного deque, в который p
вставляются новые s (разрушаемо), имейте для каждого p
свой собственный (неизменный) поток 1,0,0,1,0,0,1,...
(это для 3) и разбивайте их вместе с zipWith
попарно max 0 0 = 0; max 0 1 = 1;
и т. Д., Пропустив префикс из одного квадрата простого числа на следующей площади премьер. И [x|u==0]
сохраняет числа для 0, которые все еще там. При использовании Sieve of Eratosthenes вычисления выполняются намного быстрее по сравнению с «общеизвестным» алгоритмом простых чисел.
Используя псевдокод из его вики ( 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 мс.
ПРИМЕЧАНИЕ . Значение может отличаться в зависимости от технических характеристик оборудования.
count=0
и увеличивать его каждый раз , когда ваше множество а правда mark[j]
в false
. Таким образом, в конце вы получите правильное количество и сможете разместить массив напрямую, без предварительного создания списка. Я трачу некоторое время на написание программы, вычисляющей много простых чисел, и этот код я использую для вычисления текстового файла, содержащего первые 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);
}
}
}
Я написал это с использованием 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))
Я работал над поиском простых чисел около года. Вот что я нашел самым быстрым:
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.
Вот мой код, который находит первые 10000 простых чисел за 0,049655 с на моем ноутбуке, первые 1 000 000 простых чисел менее чем за 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);
}
Вот код, который я сделал:
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;
}
Использование метода 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
Я могу дать вам несколько советов, вы должны реализовать это.
- За каждое число получите половину этого числа. Например, для проверки 21, только получить остаток, разделив его от диапазона 2-10.
- Если это нечетное число, делите только на нечетное число, и наоборот. Например, для 21, разделите только на 3, 5, 7, 9.
Самый эффективный метод, который я получил до сих пор.
Поскольку вы хотите только первые 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
}
}
Это старый вопрос, но здесь есть что-то, чего всем не хватает ...
Для простых чисел это небольшое пробное деление не такое медленное ... есть только 25 простых чисел до 100. С таким небольшим числом простых чисел для тестирования и такими маленькими простыми числами мы можем извлечь аккуратный трюк!
Если a взаимно прост с b, то gcd ab = 1. Простое. Веселое слово. Означает, что это не имеет общих факторов . Таким образом, мы можем проверить делимость на несколько простых чисел одним вызовом GCD. Как много? Что ж, произведение первых 15 простых чисел составляет менее 2 ^ 64. И произведение следующих 10 также меньше 2 ^ 64. Это все, что нам нужно. Но стоит ли это того?
Давайте посмотрим:
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)
6-кратное улучшение там.
( length
принудительно вычисляет список. По умолчанию Haskell печатает по 1 символу Unicode за раз, поэтому фактическая печать списка будет либо доминировать во времени, либо доминировать в объеме используемого кода.)
Конечно, это работает в GHCi - repl, выполняющем интерпретированный код - на старом ноутбуке, и оно не интерпретирует ни одно из этих чисел как int64
s или даже BigInt
s, и не будет, даже если вы попросите его (ну, вы можете принудительно заставить его , но это некрасиво и не очень помогает). Он интерпретирует каждое отдельное число как обобщенные целочисленные объекты, которые могут быть специализированы для определенного типа через поиск по словарю, и пересекает связанный список (который не слит здесь, поскольку он не скомпилирован) 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. Некоторые линии обрезаны, потому что они не релевантны - они были другими данными ГХ или измерениями только части выполнения и вместе составляют в сумме 0,004 с (или меньше). Это также не постоянное сворачивание, потому что Хаскелл фактически не делает этого. Если мы будем постоянно сворачивать себя ( 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
, но определенно есть место для большей оптимизации. Например, он прекратил выполнять GC там, в то время как при настройке не должно быть никакого использования кучи. По какой-то причине компиляция для профилирования сокращает время выполнения до 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)
Я собираюсь оставить все как есть, я уверен, что случайный джиттер начинает доминировать.
using System;
namespace ConsoleApplication2
{
class Program
{
static void Main(string[] args)
{
int n, i = 3, j, c;
Console.WriteLine("Please enter your integer: ");
n = Convert.ToInt32(Console.ReadLine());
if (n >= 1)
{
Console.WriteLine("First " + n + " Prime Numbers are");
Console.WriteLine("2");
}
for(j=2;j<=n;)
{
for(c=2;c<=i-1;c++)
{
if(i%c==0)
break;
}
if(c==i)
{
Console.WriteLine(i);
j++;
}
i++;
}
Console.Read();
}
}
}