Самый эффективный код для первых 10 000 простых чисел?
https://stackoverflow.com/questions/622
-
08-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я хочу напечатать первые 10000 простых чисел.Может ли кто-нибудь дать мне наиболее эффективный код для этого?Уточнения:
- Не имеет значения, если ваш код неэффективен при n >10000.
- Размер кода не имеет значения.
- Вы не можете просто жестко закодировать значения каким-либо образом.
Решение
Решето Аткина вероятно, это то, что вы ищете, его верхняя граница времени работы равна O (N/log log N).
Если вы используете числа только на 1 больше и на 1 меньше, чем числа, кратные 6, это может быть еще быстрее, поскольку все простые числа выше 3 отстоят на 1 от некоторого числа, кратного шести.Ресурс для моего заявления
Другие советы
Я рекомендую сито, либо Решето Эратосфена или Сито Аткина.
Решето или Эратосфен, пожалуй, самый интуитивный метод поиска списка простых чисел.В основном вы:
- Запишите список чисел от 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/
Исходный код «Решета Аткина»: http://cr.yp.to/primegen.html
Это не строго противоречит ограничениям жесткого кодирования, но очень близко к этому.Почему бы вместо этого не загрузить этот список программно и не распечатать его?
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 без каких-либо составных чисел, где составные числа находятся путем перечисления кратных каждому простому числу.":
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)).
@Мэтт:журнал (журнал (10000)) равен ~ 2
Из статьи в Википедии (которую вы процитировали) Сито Аткина:
Это сито вычисляет числа промысла до n, используя
O(N/log log N)Операции только с n1/2+о(1) биты памяти.Это немного лучше, чем сито Эратостена, которое используетO(N)операции и O(N1/2(log log n)/log n) биты памяти (А.О.Л.Аткин, Д.Дж.Бернштейн, 2004).Эти асимптотические вычислительные сложности включают простую оптимизацию, такую как факторизация колеса, и разделение вычислений на меньшие блоки.
Учитывая асимптотические вычислительные сложности вдоль O(N) (для Эратосфена) и O(N/log(log(N))) (по Аткину) мы не можем сказать (по малому N=10_000), какой алгоритм, если он будет реализован, будет быстрее.
Ахим Фламменкамп писал в Решето Эратосфена:
цитирует:
@номер1
Для интервалов больше около 10^9, несомненно, для тех, что> 10^10, сито эратостенеса превосходит сито Аткинс и Бернштейн, в котором используется неприводимые двоичные квадратичные формы.Смотрите их статью о фоновой информации, а также в пункте 5 W.Доктор философии Голуэя.Тезис.
Поэтому для 10_000 Решето Эратосфена может быть быстрее, чем Решето Аткина.
Чтобы ответить на ОП, код 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+$/
Это проверяет, если для строки, состоящей из к “1”с, к является не премьер (т.е.состоит ли строка из одного «1» или любое количество «1», что можно выразить как н-арный продукт).
Я адаптировал код, найденный на КодПроект чтобы создать следующее:
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 минуты.
Вот решето Эратосфена, которое я написал в 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
Адаптация и продолжение 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;
}
По сути, это то же самое, но я добавил предложение «прервать Sqrt» и изменил некоторые переменные, чтобы оно лучше подходило мне.(Я работал над Эйлером, и мне нужно было 10001-е простое число)
Кажется, «Сито» — неправильный ответ.Сито дает вам простые числа вплоть до число Н, не первый Н простые числа.Запустите @Imran или @Andrew Szeto, и вы получите простые числа до N.
Сито все еще можно использовать, если вы продолжаете пробовать сита для все больших чисел, пока не достигнете определенного размера вашего набора результатов, и используете некоторое кэширование уже полученных чисел, но я считаю, что это все равно будет не быстрее, чем такое решение, как @Pat's. .
На Python
import gmpy
p=1
for i in range(10000):
p=gmpy.next_prime(p)
print p
А алгоритм дек-сита, упомянутый Бенгольдбергом заслуживает более пристального внимания не только потому, что оно очень элегантно, но и потому, что иногда может быть полезно на практике (в отличие от «Решета Аткина», которое является чисто академическим упражнением).
Основная идея алгоритма deque sieve заключается в использовании небольшого скользящего сита, достаточно большого для того, чтобы содержать хотя бы одно отдельное кратное для каждого из «активных» в данный момент простых множителей, т.е.те простые числа, квадрат которых не превышает наименьшее число, представленное в данный момент движущимся решетом.Еще одно отличие от SoE состоит в том, что фильтр deque сохраняет фактические коэффициенты в слотах составных чисел, а не логические значения.
Алгоритм увеличивает размер сито по мере необходимости, что приводит к довольно равномерной производительности в широком диапазоне до тех пор, пока сито не начнет заметно превышать емкость кэша L1 ЦП.Последнее полностью подходящее простое число — 25 237 523 (1 579 791-е простое число), что дает приблизительную приблизительную цифру для разумного рабочего диапазона алгоритма.
Алгоритм довольно прост и надежен, и его производительность даже в гораздо более широком диапазоне, чем у несегментированного Решета Эратосфена.Последний работает намного быстрее, если его сито полностью помещается в кэш, т.е.до 2^16 для сита только для шансов с логическими значениями размером в байт.Затем его производительность падает все больше и больше, хотя он всегда остается значительно быстрее дека, несмотря на недостатки (по крайней мере, в компилируемых языках, таких как C/C++, Pascal или Java/C#).
Вот визуализация алгоритма deque sieve на C#, потому что я считаю, что этот язык - несмотря на его многочисленные недостатки - гораздо более практичен для прототипирования алгоритмов и экспериментов, чем чрезвычайно громоздкий и педантичный C++. (Примечание:Я использую бесплатный LINQPad что позволяет сразу приступить к делу, без всякой путаницы с настройкой проектов, make-файлов, каталогов и т. д., и это дает мне ту же степень интерактивности, что и приглашение Python).
В C# нет явного типа deque, но есть простой List<int> работает достаточно хорошо для демонстрации алгоритма.
Примечание:эта версия не использует дек для простых чисел, потому что просто не имеет смысла извлекать 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 не может быть кратным любому из простых чисел, меньших текущего простого числа, иначе оно было бы помечено как составное.I также не может быть кратным текущему простому числу, поскольку его значение меньше квадрата текущего простого числа.Следовательно, это должно быть новое простое число.
Алгоритм, очевидно, вдохновлен «Решетом Эратосфена», но столь же очевидно, что он сильно отличается.Решето Эратосфена обеспечивает свою превосходную скорость благодаря простоте его элементарных операций:одно добавление индекса и одно сохранение для каждого шага операции — это все, что он делает в течение длительного периода времени.
Вот простое несегментированное решето Эратосфена, которое я обычно использую для просеивания простых чисел в коротком диапазоне, т.е.до 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++, потому что я хотел, чтобы он был основан на предположительно адекватном типе дека (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> это не проблема, даже если использовать его как дек.
Простой код Sieve по-прежнему выбрасывает дек из воды, даже несмотря на то, что он уже работает за пределами нормального рабочего диапазона (размер кэша L1 превышен на 50%, что сопровождается перегрузкой кэша).Доминирующей частью здесь является считывание просеянных простых чисел, и на это не сильно влияет проблема с кэшем.В любом случае функция была предназначена для отсеивания факторов из факторов, т.е.уровень 0 в трехуровневой ситовой иерархии, и обычно он должен возвращать только несколько сотен факторов или небольшое количество тысяч.Отсюда его простота.
Производительность можно повысить более чем на порядок, используя сегментированное сито и оптимизируя код для извлечения просеянных простых чисел (ступенчатый мод 3 и разворачивается дважды, или мод 15 и разворачивается один раз), и еще больше производительности можно выжать из кода, используя колесо Mod 16 или Mod 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, все может выглядеть совершенно по-другому, где каждая операция имеет большие затраты, а накладные расходы интерпретатора затмевают все различия из-за прогнозируемых и ожидаемых результатов.неправильно предсказанные ветки или операции подцикла (сдвиг, сложение) илимногоцикловые операции (умножение и, возможно, даже деление).Это неизбежно разрушит преимущество простоты Решета Эратосфена, и это может сделать решение deque немного более привлекательным.
Кроме того, во многих случаях, о которых сообщили другие респонденты в этой теме, вероятно, преобладают время вывода.Это совсем другая война, где моим главным оружием является такой простой класс:
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;
}
}
}
Для записи 10 000 (отсортированных) чисел требуется менее 1 мс.Это статический класс, поскольку он предназначен для текстового включения в заявки на кодирование с минимумом суеты и нулевыми накладными расходами.
В общем я нашел это много быстрее, если целенаправленная работа выполняется над целыми пакетами, то есть просеивать определенный диапазон, затем извлекать все простые числа в вектор/массив, затем выбрасывать весь массив, затем просеивать следующий диапазон и так далее, вместо того, чтобы смешивать все вместе.Наличие отдельных функций, ориентированных на конкретные задачи, также облегчает смешивание и сопоставление, позволяет повторно использовать и упрощает разработку/тестирование.
Вот мой код VB 2008, который находит все простые числа <10 000 000 за 1 минуту 27 секунд на моем рабочем ноутбуке.Он пропускает четные числа и ищет только простые числа, которые < sqrt проверочного числа.Он предназначен только для поиска простых чисел от 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;
}
Обратите внимание, что эта версия Sieve может вычислять простые числа бесконечно.
Также обратите внимание, что STL deque берет O(1) время выступать push_back, pop_front, и произвольный доступ посредством подписки.
А resize операция занимает O(n) время, где n — количество добавляемых элементов.Благодаря тому, как мы используем эту функцию, мы можем считать ее небольшой константой.
Тело while зациклиться my_insert выполняется O(log log n) времена, где n равно переменной maybe_prime.Это связано с тем, что выражение условия while будет иметь значение true один раз для каждого простого фактора maybe_prime.Видеть "Функция делителя" в Википедии.
Умножение на количество раз my_insert вызывается, показывает, что следует принять O(n log log n) пора перечислять n простые числа...что, неудивительно, и есть временная сложность, которой должно обладать Решето Эратосфена.
Однако, хотя этот код является эффективный, это не Наиболее эффективным...Я настоятельно рекомендую использовать специализированную библиотеку для генерации простых чисел, например простое сито.Любое по-настоящему эффективное и хорошо оптимизированное решение потребует больше кода, чем кто-либо захочет ввести в Stackoverflow.
Используя Решето Эратосфена, вычисления выполняются намного быстрее по сравнению с «общеизвестным» алгоритмом простых чисел.
Используя псевдокод из его вики (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 мс.
ПРИМЕЧАНИЕ:Значение может варьироваться в зависимости от технических характеристик оборудования.
Я трачу некоторое время на написание программы, вычисляющей множество простых чисел, и это код, который я использую для вычисления текстового файла, содержащего первые 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, так как только начал его изучать, и он работает отлично.10 000-е простое число генерируется с помощью этого кода так же, как указано в 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.
Вот мой кодекс, который находит первые 10 000 простых числа за 0,049655 секунды на моем ноутбуке, первые 1 000 000 простых числа за 6 секунд и первые 2 000 000 за 15 секунд
Небольшое объяснение.Этот метод использует 2 метода для поиска простого числа.
- Прежде всего, любое непростое число является составным из кратных простых чисел, поэтому этот тест кода путем деления тестового числа на меньшие простые числа вместо любого числа, это уменьшает расчет как минимум в 10 раз для 4-значного числа и даже больше для большее число
- во-вторых, помимо деления на простое число, он делится только на простые числа, которые меньше или равны корню проверяемого числа, что еще больше сокращает вычисления, это работает, потому что любое число, которое больше корня числа, будет иметь соответствующее число, которое должно быть меньше корня числа, но поскольку мы уже проверили все числа, меньшие корня числа, поэтому нам не нужно беспокоиться о числе, большем корня проверяемого числа.
Пример вывода для первых 10 000 простых чисел
https://drive.google.com/open?id=0B2QYXBiLI-lZMUpCNFhZeUphck0 https://drive.google.com/open?id=0B2QYXBiLI-lZbmRtTkZETnp6Ykk
Вот код на языке C, введите 1, а затем 10 000, чтобы распечатать первые 10 000 простых чисел.
Редактировать:Я забыл, что здесь содержится математическая библиотека. Если вы используете 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
}
}
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();
}
}
}
