Увлекательное вычисление простых чисел
https://stackoverflow.com/questions/288200
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Мы немного развлекаемся здесь, на работе.Все началось с того, что один из парней установил Hackintosh, и нам стало интересно, быстрее ли он, чем Windows Box с (почти) теми же характеристиками, что и у нас.Поэтому мы решили написать для него небольшой тест.Просто простой калькулятор простых чисел.Он написан на Java и сообщает нам время, необходимое для вычисления первых n простых чисел.
Оптимизированная версия ниже — теперь занимает ~6,6 секунд.
public class Primes {
public static void main(String[] args) {
int topPrime = 150000;
int current = 2;
int count = 0;
int lastPrime = 2;
long start = System.currentTimeMillis();
while (count < topPrime) {
boolean prime = true;
int top = (int)Math.sqrt(current) + 1;
for (int i = 2; i < top; i++) {
if (current % i == 0) {
prime = false;
break;
}
}
if (prime) {
count++;
lastPrime = current;
}
if (current == 2) {
current++;
} else {
current = current + 2;
}
}
System.out.println("Last prime = " + lastPrime);
System.out.println("Total time = " + (double)(System.currentTimeMillis() - start) / 1000);
}
}
Мы практически утратили смысл всей этой истории с Хакинтошем против ПК и просто развлекаемся его оптимизацией.Первая попытка без оптимизации (в приведенном выше коде есть пара) заняла около 52,6 минут, чтобы найти первые 150 000 простых чисел.Эта оптимизация длится около 47,2 минуты.
Если вы хотите попробовать и опубликовать свои результаты, прикрепите их.
Характеристики компьютера, на котором я его запускаю, — Pentium D 2,8 ГГц, 2 ГБ ОЗУ и Ubuntu 8.04.
Лучшей оптимизацией на данный момент является квадратный корень из текущего, впервые упомянутый Джейсоном З.
Решение
Что ж, я вижу пару быстрых оптимизаций, которые можно сделать.Во-первых, вам не придется пробовать каждое число до половины текущего числа.
Вместо этого вам нужно только попытаться найти квадратный корень из текущего числа.
Другая оптимизация заключалась в том, что BP сказала с изюминкой:Вместо
int count = 0;
...
for (int i = 2; i < top; i++)
...
if (current == 2)
current++;
else
current += 2;
использовать
int count = 1;
...
for (int i = 3; i < top; i += 2)
...
current += 2;
Это должно значительно ускорить процесс.
Редактировать:
Дополнительная оптимизация предоставлена Джо Пинедой:
Удалите переменную «top».
int count = 1;
...
for (int i = 3; i*i <= current; i += 2)
...
current += 2;
Если эта оптимизация действительно увеличивает скорость, это зависит от java.
Вычисление квадратного корня занимает много времени по сравнению с умножением двух чисел.Однако, поскольку мы перемещаем умножение в цикл for, это выполняется в каждом цикле.Таким образом, это МОЖЕТ замедлить работу в зависимости от того, насколько быстр алгоритм квадратного корня в Java.
Другие советы
Это немного хуже, чем мое сито на 8 МГц 8088 в турбо паскале в 1986 году или около того. Но это было после оптимизаций:)
Поскольку вы ищете их в порядке возрастания, вы можете хранить список простых чисел, которые вы уже нашли, и проверять только делимость на них, поскольку все не простые числа можно сократить до списка меньших простых факторы. Добавьте к этому предыдущий совет о том, что не нужно проверять факторы по квадратному корню из текущего числа, и вы получите чертовски эффективную реализацию.
Вот быстрое и простое решение:
- Нахождение простых чисел меньше 100000;9592 найдено за 5 мс
- Нахождение простых чисел меньше 1000000;78498 было найдено за 20 мс
- Нахождение простых чисел меньше 10000000;664579 было найдено за 143 мс
- Нахождение простых чисел меньше 100000000;5761455 было найдено за 2024 мс.
Нахождение простых чисел меньше 1000000000;50847534 были найдены за 23839 мс.
//returns number of primes less than n private static int getNumberOfPrimes(final int n) { if(n < 2) return 0; BitSet candidates = new BitSet(n - 1); candidates.set(0, false); candidates.set(1, false); candidates.set(2, n); for(int i = 2; i < n; i++) if(candidates.get(i)) for(int j = i + i; j < n; j += i) if(candidates.get(j) && j % i == 0) candidates.set(j, false); return candidates.cardinality(); }
Нам требуется менее секунды (2,4 ГГц), чтобы сгенерировать первые 150 000 простых чисел в Python с помощью Решета Эратосфена:
#!/usr/bin/env python
def iprimes_upto(limit):
"""Generate all prime numbers less then limit.
http://stackoverflow.com/questions/188425/project-euler-problem#193605
"""
is_prime = [True] * limit
for n in range(2, limit):
if is_prime[n]:
yield n
for i in range(n*n, limit, n): # start at ``n`` squared
is_prime[i] = False
def sup_prime(n):
"""Return an integer upper bound for p(n).
p(n) < n (log n + log log n - 1 + 1.8 log log n / log n)
where p(n) is the n-th prime.
http://primes.utm.edu/howmany.shtml#2
"""
from math import ceil, log
assert n >= 13
pn = n * (log(n) + log(log(n)) - 1 + 1.8 * log(log(n)) / log(n))
return int(ceil(pn))
if __name__ == '__main__':
import sys
max_number_of_primes = int(sys.argv[1]) if len(sys.argv) == 2 else 150000
primes = list(iprimes_upto(sup_prime(max_number_of_primes)))
print("Generated %d primes" % len(primes))
n = 100
print("The first %d primes are %s" % (n, primes[:n]))
Пример:
$ python primes.py
Generated 153465 primes
The first 100 primes are [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, 101, 103, 107, 109, 113,
127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197,
199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379,
383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
467, 479, 487, 491, 499, 503, 509, 521, 523, 541]
В С#:
class Program
{
static void Main(string[] args)
{
int count = 0;
int max = 150000;
int i = 2;
DateTime start = DateTime.Now;
while (count < max)
{
if (IsPrime(i))
{
count++;
}
i++;
}
DateTime end = DateTime.Now;
Console.WriteLine("Total time taken: " + (end - start).TotalSeconds.ToString() + " seconds");
Console.ReadLine();
}
static bool IsPrime(int n)
{
if (n < 4)
return true;
if (n % 2 == 0)
return false;
int s = (int)Math.Sqrt(n);
for (int i = 2; i <= s; i++)
if (n % i == 0)
return false;
return true;
}
}
Выход:
Всего затрачено времени:2,087 секунды
Имея в виду, что есть более эффективные способы поиска простых чисел...
Я думаю, что вы можете взять этот цикл:
for (int i = 2; i < top; i++)
и сделайте так, чтобы ваша переменная-счетчик i начиналась с 3 и пыталась выполнить модификацию только с нечетными числами, поскольку все простые числа, кроме 2, никогда не делятся ни на какие четные числа.
Выполняет ли повторное объявление переменной prime
while (count < topPrime) {
boolean prime = true;
внутри цикла сделать его неэффективным? (Полагаю, это не имеет значения, поскольку я думаю, что Java оптимизирует это)
boolean prime;
while (count < topPrime) {
prime = true;
С#
Улучшение Код Айстины:
При этом используется тот факт, что все простые числа больше 3 имеют вид 6n + 1 или 6n - 1.
Это было увеличение скорости примерно на 4-5% по сравнению с приращением на 1 за каждый проход по циклу.
class Program
{
static void Main(string[] args)
{
DateTime start = DateTime.Now;
int count = 2; //once 2 and 3
int i = 5;
while (count < 150000)
{
if (IsPrime(i))
{
count++;
}
i += 2;
if (IsPrime(i))
{
count++;
}
i += 4;
}
DateTime end = DateTime.Now;
Console.WriteLine("Total time taken: " + (end - start).TotalSeconds.ToString() + " seconds");
Console.ReadLine();
}
static bool IsPrime(int n)
{
//if (n < 4)
//return true;
//if (n % 2 == 0)
//return false;
int s = (int)Math.Sqrt(n);
for (int i = 2; i <= s; i++)
if (n % i == 0)
return false;
return true;
}
}
Мой взгляд на оптимизацию, избегая слишком загадочных трюков.Я использую трюк, данный Я-ДАЮ-УЖАСНЫЙ-СОВЕТ, который я знал и забыл...:-)
public class Primes
{
// Original code
public static void first()
{
int topPrime = 150003;
int current = 2;
int count = 0;
int lastPrime = 2;
long start = System.currentTimeMillis();
while (count < topPrime) {
boolean prime = true;
int top = (int)Math.sqrt(current) + 1;
for (int i = 2; i < top; i++) {
if (current % i == 0) {
prime = false;
break;
}
}
if (prime) {
count++;
lastPrime = current;
// System.out.print(lastPrime + " "); // Checking algo is correct...
}
if (current == 2) {
current++;
} else {
current = current + 2;
}
}
System.out.println("\n-- First");
System.out.println("Last prime = " + lastPrime);
System.out.println("Total time = " + (double)(System.currentTimeMillis() - start) / 1000);
}
// My attempt
public static void second()
{
final int wantedPrimeNb = 150000;
int count = 0;
int currentNumber = 1;
int increment = 4;
int lastPrime = 0;
long start = System.currentTimeMillis();
NEXT_TESTING_NUMBER:
while (count < wantedPrimeNb)
{
currentNumber += increment;
increment = 6 - increment;
if (currentNumber % 2 == 0) // Even number
continue;
if (currentNumber % 3 == 0) // Multiple of three
continue;
int top = (int) Math.sqrt(currentNumber) + 1;
int testingNumber = 5;
int testIncrement = 2;
do
{
if (currentNumber % testingNumber == 0)
{
continue NEXT_TESTING_NUMBER;
}
testingNumber += testIncrement;
testIncrement = 6 - testIncrement;
} while (testingNumber < top);
// If we got there, we have a prime
count++;
lastPrime = currentNumber;
// System.out.print(lastPrime + " "); // Checking algo is correct...
}
System.out.println("\n-- Second");
System.out.println("Last prime = " + lastPrime);
System.out.println("Total time = " + (double) (System.currentTimeMillis() - start) / 1000);
}
public static void main(String[] args)
{
first();
second();
}
}
Да, я использовал помеченное продолжение, впервые пробую их на Java...
Я знаю, что пропускаю вычисление первых нескольких простых чисел, но они хорошо известны, и нет смысла их пересчитывать.:-) При необходимости я могу жестко запрограммировать их вывод!Да и решающего преимущества это все равно не дает.
Полученные результаты:
-- Первый
Последнее простое число = 2015201
Общее время = 4.281
-- Второй
Последнее простое число = 2015201
Общее время = 0,953
Неплохо.Полагаю, его можно немного улучшить, но слишком большая оптимизация может убить хороший код.
Вы должны быть в состоянии сделать внутренний цикл в два раза быстрее, вычисляя только нечетные числа. Не уверен, что это допустимый Java, я привык к C ++, но уверен, что его можно адаптировать.
if (current != 2 && current % 2 == 0)
prime = false;
else {
for (int i = 3; i < top; i+=2) {
if (current % i == 0) {
prime = false;
break;
}
}
}
Я решил попробовать это в F #, моей первой достойной попытке. Используя сито эратосфена на моем 2,2 ГГц Core 2 Duo, он проходит через 2,150 000 примерно за 200 миллисекунд. Каждый раз, когда он называет себя сам, он удаляет текущие кратные значения из списка, поэтому он просто становится быстрее по мере продвижения. Это одна из моих первых попыток в F #, поэтому любые конструктивные комментарии приветствуются.
let max = 150000
let numbers = [2..max]
let rec getPrimes sieve max =
match sieve with
| [] -> sieve
| _ when sqrt(float(max)) < float sieve.[0] -> sieve
| _ -> let prime = sieve.[0]
let filtered = List.filter(fun x -> x % prime <> 0) sieve // Removes the prime as well so the recursion works correctly.
let result = getPrimes filtered max
prime::result // The filter removes the prime so add it back to the primes result.
let timer = System.Diagnostics.Stopwatch()
timer.Start()
let r = getPrimes numbers max
timer.Stop()
printfn "Primes: %A" r
printfn "Elapsed: %d.%d" timer.Elapsed.Seconds timer.Elapsed.Milliseconds
Бьюсь об заклад, Миллер-Рабин будет быстрее. Если вы протестируете достаточно смежные числа, это станет детерминированным, но я бы даже не стал беспокоиться. Как только рандомизированный алгоритм достигнет точки, в которой частота отказов будет равна вероятности того, что сбой процессора вызовет неправильный результат, это уже не имеет значения.
Вот мое решение ... оно довольно быстрое ... оно рассчитывает простые числа от 1 до 10 000 000 за 3 секунды на моей машине (core i7 @ 2.93Ghz) в Vista64.
Мое решение на C, но я не профессиональный программист на C. Не стесняйтесь критиковать алгоритм и сам код:)
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<time.h>
//5MB... allocate a lot of memory at once each time we need it
#define ARRAYMULT 5242880
//list of calculated primes
__int64* primes;
//number of primes calculated
__int64 primeCount;
//the current size of the array
__int64 arraySize;
//Prints all of the calculated primes
void PrintPrimes()
{
__int64 i;
for(i=0; i<primeCount; i++)
{
printf("%d ", primes[i]);
}
}
//Calculates all prime numbers to max
void CalcPrime(__int64 max)
{
register __int64 i;
double square;
primes = (__int64*)malloc(sizeof(__int64) * ARRAYMULT);
primeCount = 0;
arraySize = ARRAYMULT;
//we provide the first prime because its even, and it would be convenient to start
//at an odd number so we can skip evens.
primes[0] = 2;
primeCount++;
for(i=3; i<max; i+=2)
{
int j;
square = sqrt((double)i);
//only test the current candidate against other primes.
for(j=0; j<primeCount; j++)
{
//prime divides evenly into candidate, so we have a non-prime
if(i%primes[j]==0)
break;
else
{
//if we've reached the point where the next prime is > than the square of the
//candidate, the candidate is a prime... so we can add it to the list
if(primes[j] > square)
{
//our array has run out of room, so we need to expand it
if(primeCount >= arraySize)
{
int k;
__int64* newArray = (__int64*)malloc(sizeof(__int64) * (ARRAYMULT + arraySize));
for(k=0; k<primeCount; k++)
{
newArray[k] = primes[k];
}
arraySize += ARRAYMULT;
free(primes);
primes = newArray;
}
//add the prime to the list
primes[primeCount] = i;
primeCount++;
break;
}
}
}
}
}
int main()
{
int max;
time_t t1,t2;
double elapsedTime;
printf("Enter the max number to calculate primes for:\n");
scanf_s("%d",&max);
t1 = time(0);
CalcPrime(max);
t2 = time(0);
elapsedTime = difftime(t2, t1);
printf("%d Primes found.\n", primeCount);
printf("%f seconds elapsed.\n\n",elapsedTime);
//PrintPrimes();
scanf("%d");
return 1;
}
Вот мое мнение. Программа написана на языке C и занимает 50 миллисекунд на моем ноутбуке (Core 2 Duo, 1 ГБ Ram). Я сохраняю все вычисленные простые числа в массиве и пытаюсь делиться только до sqrt числа. Конечно, это не работает, когда нам нужно очень большое количество простых чисел (пробовал с 100000000), так как массив становится слишком большим и дает ошибку сегмента.
/*Calculate the primes till TOTALPRIMES*/
#include <stdio.h>
#define TOTALPRIMES 15000
main(){
int primes[TOTALPRIMES];
int count;
int i, j, cpr;
char isPrime;
primes[0] = 2;
count = 1;
for(i = 3; count < TOTALPRIMES; i+= 2){
isPrime = 1;
//check divisiblity only with previous primes
for(j = 0; j < count; j++){
cpr = primes[j];
if(i % cpr == 0){
isPrime = 0;
break;
}
if(cpr*cpr > i){
break;
}
}
if(isPrime == 1){
//printf("Prime: %d\n", i);
primes[count] = i;
count++;
}
}
printf("Last prime = %d\n", primes[TOTALPRIMES - 1]);
}
$ time ./a.out Last prime = 163841 real 0m0.045s user 0m0.040s sys 0m0.004s
@ Марк Рэнсом - не уверен, что это код Java
Они будут стонать , возможно, , но я хотел переписать, используя парадигму, которую я научился доверять Java, и они сказали, что повеселиться, пожалуйста, убедитесь, что они понимают, что спецификация ничего не говорит, что влияет на порядок возвращенный набор результатов, также вы приведете значения точек набора результатов () к типу списка, указанному в блокноте, перед тем как выполнить короткое поручение
=============== начать непроверенный код ===============
package demo;
import java.util.List;
import java.util.HashSet;
class Primality
{
int current = 0;
int minValue;
private static final HashSet<Integer> resultSet = new HashSet<Integer>();
final int increment = 2;
// An obvious optimization is to use some already known work as an internal
// constant table of some kind, reducing approaches to boundary conditions.
int[] alreadyKown =
{
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, 101, 103, 107, 109, 113,
127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197,
199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379,
383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
467, 479, 487, 491, 499, 503, 509, 521, 523, 541
};
// Trivial constructor.
public Primality(int minValue)
{
this.minValue = minValue;
}
List calcPrimes( int startValue )
{
// eliminate several hundred already known primes
// by hardcoding the first few dozen - implemented
// from prior work by J.F. Sebastian
if( startValue > this.minValue )
{
// Duh.
current = Math.abs( start );
do
{
boolean prime = true;
int index = current;
do
{
if(current % index == 0)
{
// here, current cannot be prime so break.
prime = false;
break;
}
while( --index > 0x00000000 );
// Unreachable if not prime
// Here for clarity
if ( prime )
{
resultSet dot add ( or put or whatever it is )
new Integer ( current ) ;
}
}
while( ( current - increment ) > this.minValue );
// Sanity check
if resultSet dot size is greater that zero
{
for ( int anInt : alreadyKown ) { resultSet.add( new Integer ( anInt ) );}
return resultSet;
}
else throw an exception ....
}
=============== конец непроверенного кода ===============
Использование хеш-наборов позволяет искать результаты в виде B-деревьев, поэтому результаты могут накапливаться до тех пор, пока машина не начнет выходить из строя, тогда эту начальную точку можно использовать для другого блока тестирования == конец одного прогона, используемый в качестве значения конструктора для другого запуска - сохранение работы диска, уже выполненной, и допущение дополняющего проектирования с прямой связью. Сгорел прямо сейчас, логика цикла нуждается в анализе.
исправление (плюс добавление sqrt):
if(current % 5 == 0 )
if(current % 7 == 0 )
if( ( ( ( current % 12 ) +1 ) == 0) || ( ( ( current % 12 ) -1 ) == 0) ){break;}
if( ( ( ( current % 18 ) +1 ) == 0) || ( ( ( current % 18 ) -1 ) == 0) ){break;}
if( ( ( ( current % 24 ) +1 ) == 0) || ( ( ( current % 24 ) -1 ) == 0) ){break;}
if( ( ( ( current % 36 ) +1 ) == 0) || ( ( ( current % 36 ) -1 ) == 0) ){break;}
if( ( ( ( current % 24 ) +1 ) == 0) || ( ( ( current % 42 ) -1 ) == 0) ){break;}
// and - new work this morning:
package demo;
/**
*
* Buncha stuff deleted for posting .... duh.
*
* @author Author
* @version 0.2.1
*
* Note strings are base36
*/
public final class Alice extends java.util.HashSet<java.lang.String>
{
// prints 14551 so it's 14 ½ seconds to get 40,000 likely primes
// using Java built-in on amd sempron 1.8 ghz / 1600 mhz front side bus 256 k L-2
public static void main(java.lang.String[] args)
{
try
{
final long start=System.currentTimeMillis();
// VM exhibits spurious 16-bit pointer behaviour somewhere after 40,000
final java.lang.Integer upperBound=new java.lang.Integer(40000);
int index = upperBound.intValue();
final java.util.HashSet<java.lang.String>hashSet
= new java.util.HashSet<java.lang.String>(upperBound.intValue());//
// Arbitraily chosen value, based on no idea where to start.
java.math.BigInteger probablePrime
= new java.math.BigInteger(16,java.security.SecureRandom.getInstance("SHA1PRNG"));
do
{
java.math.BigInteger nextProbablePrime = probablePrime.nextProbablePrime();
if(hashSet.add(new java.lang.String(nextProbablePrime.toString(Character.MAX_RADIX))))
{
probablePrime = nextProbablePrime;
if( ( index % 100 ) == 0x00000000 )
{
// System.out.println(nextProbablePrime.toString(Character.MAX_RADIX));//
continue;
}
else
{
continue;
}
}
else
{
throw new StackOverflowError(new String("hashSet.add(string) failed on iteration: "+
Integer.toString(upperBound.intValue() - index)));
}
}
while(--index > 0x00000000);
System.err.println(Long.toString( System.currentTimeMillis() - start));
}
catch(java.security.NoSuchAlgorithmException nsae)
{
// Never happen
return;
}
catch(java.lang.StackOverflowError soe)
{
// Might happen
System.out.println(soe.getMessage());//
return;
}
}
}// end class Alice
Я нашел этот код где-то на своей машине, когда начал читать эту запись в блоге о простых числах. Код написан на C #, а алгоритм, который я использовал, пришел из моей головы, хотя, вероятно, он где-то в Википедии. ;) В любом случае, он может получить первые 150000 простых чисел за 300 мс. Я обнаружил, что сумма n первых нечетных чисел равна n ^ 2. Снова, вероятно, есть доказательство этого где-то в Википедии. Итак, зная это, я могу написать алгоритм, который никогда не должен будет вычислять квадратный корень, но я должен вычислять постепенно, чтобы найти простые числа. Так что если вы хотите N-е простое число, этот алгоритм должен будет найти (N-1) предшествующие простые числа раньше! Так и есть. Наслаждайтесь!
//
// Finds the n first prime numbers.
//
//count: Number of prime numbers to find.
//listPrimes: A reference to a list that will contain all n first prime if getLast is set to false.
//getLast: If true, the list will only contain the nth prime number.
//
static ulong GetPrimes(ulong count, ref IList listPrimes, bool getLast)
{
if (count == 0)
return 0;
if (count == 1)
{
if (listPrimes != null)
{
if (!getLast || (count == 1))
listPrimes.Add(2);
}
return count;
}
ulong currentSquare = 1;
ulong nextSquare = 9;
ulong nextSquareIndex = 3;
ulong primesCount = 1;
List dividers = new List();
//Only check for odd numbers starting with 3.
for (ulong curNumber = 3; (curNumber (nextSquareIndex % div) == 0) == false)
dividers.Add(nextSquareIndex);
//Move to next square number
currentSquare = nextSquare;
//Skip the even dividers so take the next odd square number.
nextSquare += (4 * (nextSquareIndex + 1));
nextSquareIndex += 2;
//We may continue as a square number is never a prime number for obvious reasons :).
continue;
}
//Check if there is at least one divider for the current number.
//If so, this is not a prime number.
if (dividers.Exists(div => (curNumber % div) == 0) == false)
{
if (listPrimes != null)
{
//Unless we requested only the last prime, add it to the list of found prime numbers.
if (!getLast || (primesCount + 1 == count))
listPrimes.Add(curNumber);
}
primesCount++;
}
}
return primesCount;
}
Вот мой вклад:
Машина:Четырехъядерный процессор i7 с тактовой частотой 2,4 ГГц и 8 ГБ ОЗУ @ 1600 МГц
Компилятор: clang++ main.cpp -O3
Тесты:
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 100
Calculated 25 prime numbers up to 100 in 2 clocks (0.000002 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 1000
Calculated 168 prime numbers up to 1000 in 4 clocks (0.000004 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 10000
Calculated 1229 prime numbers up to 10000 in 18 clocks (0.000018 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 100000
Calculated 9592 prime numbers up to 100000 in 237 clocks (0.000237 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 1000000
Calculated 78498 prime numbers up to 1000000 in 3232 clocks (0.003232 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 10000000
Calculated 664579 prime numbers up to 10000000 in 51620 clocks (0.051620 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 100000000
Calculated 5761455 prime numbers up to 100000000 in 918373 clocks (0.918373 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 1000000000
Calculated 50847534 prime numbers up to 1000000000 in 10978897 clocks (10.978897 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 4000000000
Calculated 189961812 prime numbers up to 4000000000 in 53709395 clocks (53.709396 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$
Источник:
#include <iostream> // cout
#include <cmath> // sqrt
#include <ctime> // clock/CLOCKS_PER_SEC
#include <cstdlib> // malloc/free
using namespace std;
int main(int argc, const char * argv[]) {
if(argc == 1) {
cout << "Please enter a number." << "\n";
return 1;
}
long n = atol(argv[1]);
long i;
long j;
long k;
long c;
long sr;
bool * a = (bool*)malloc((size_t)n * sizeof(bool));
for(i = 2; i < n; i++) {
a[i] = true;
}
clock_t t = clock();
sr = sqrt(n);
for(i = 2; i <= sr; i++) {
if(a[i]) {
for(k = 0, j = 0; j <= n; j = (i * i) + (k * i), k++) {
a[j] = false;
}
}
}
t = clock() - t;
c = 0;
for(i = 2; i < n; i++) {
if(a[i]) {
//cout << i << " ";
c++;
}
}
cout << fixed << "\nCalculated " << c << " prime numbers up to " << n << " in " << t << " clocks (" << ((float)t) / CLOCKS_PER_SEC << " seconds).\n";
free(a);
return 0;
}
Здесь используется подход «Решета Эрастофена», я оптимизировал его настолько, насколько мог, исходя из своих знаний.Улучшения приветствуются.
