divertido cálculo número primo
https://stackoverflow.com/questions/288200
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Nós estamos tendo um pouco de diversão aqui no trabalho. Tudo começou com um dos caras criação de um Hackintosh e fomos perguntar se era mais rápido do que uma caixa de Windows de (quase) mesmas especificações que temos. Então decidimos escrever um pequeno teste para ele. Apenas um simples primeiro-calculadora número. Ele é escrito em Java e diz-nos o tempo que leva para calcular os primeiros n Prime números.
versão otimizado abaixo - agora leva ~ 6.6secs
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);
}
}
Nós praticamente perdeu o enredo da coisa toda Hackintosh vs PC e estão apenas se divertindo um pouco com otimizando-o. Primeira tentativa sem otimizações (o código acima tem um casal) correu ao redor 52.6min para encontrar os primeiros 150000 números primos. Essa otimização está correndo 47.2mins.
Se você quiser ter um ir e postar seus resultados, em seguida, ficar em up.
Specs para o PC que eu estou executando-o em são Pentium D 2,8 GHz, 2 GB de RAM, rodando Ubuntu 8.04.
Melhor Otimização até agora tem sido a raiz quadrada de corrente, mencionado pela primeira vez por Jason Z.
Solução
Bem, eu vejo um par de otimizações rápidas que podem ser feitas. Primeiro, você não tem que tentar cada número até metade do número atual.
Em vez disso você só tem tentar até a raiz quadrada do número atual.
E a outra otimização foi o que BP disse com uma torção: Em vez de
int count = 0;
...
for (int i = 2; i < top; i++)
...
if (current == 2)
current++;
else
current += 2;
uso
int count = 1;
...
for (int i = 3; i < top; i += 2)
...
current += 2;
Isso deve acelerar as coisas muito.
Editar:
Mais otimização cortesia de Joe Pineda:
Remover a variável "top".
int count = 1;
...
for (int i = 3; i*i <= current; i += 2)
...
current += 2;
Se essa otimização de fato aumenta a velocidade é de até java.
Calcular a raiz quadrada tem um monte de tempo em comparação com a multiplicação de dois números. No entanto, uma vez que mover a multiplicação no loop for isso é feito a cada circuito único. Assim que este poderia retardar as coisas dependendo de quão rápido o algoritmo de raiz quadrada em java é.
Outras dicas
Isso é um pouco pior do que a minha peneira fiz em um 8 Mhz 8088 no turbo pascal em 1986 ou assim. Mas isso foi depois de otimizações:)
Uma vez que você está procurando-los em ordem crescente, você poderia manter uma lista dos números primos você já encontrou e só verificar divisibilidade contra eles, já que todos os números não-prime pode ser reduzida a uma lista de menor primo fatores. Combine isso com a dica anterior sobre não verificação de fatores sobre a raiz quadrada do número atual, e você terá a si mesmo uma implementação eficiente danado bonito.
Aqui está uma solução rápida e simples:
- Finding primos menos de 100000; 9592 foram encontrados em 5 ms
- Finding primos menos de 1000000; 78.498 foram encontrados em 20 ms
- Finding primos menos de 10000000; 664.579 foram encontrados em 143 ms
- Finding primos inferior a 100000000; 5761455 foram encontrados em 2024 ms
-
Finding primos menos de 1000000000; 50847534 foram encontrados em 23839 ms
//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(); }
Ela nos leva menos de um segundo (2,4 GHz) para gerar os primeiros 150000 números primos em Python utilizando Crivo de Eratóstenes:
#!/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]))
Exemplo:
$ 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]
Em C #:
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;
}
}
Output:
Tempo total: 2.087 segundos
Tendo em mente que há melhores maneiras de olhar para primos ...
Eu acho que você pode tomar este loop:
for (int i = 2; i < top; i++)
e fazer com que a sua variável de contador i vai de 3 e só tenta fazer a modificação em números ímpares, já que todos os outros que 2 primos não são divisíveis por quaisquer números pares.
Será que a re-declaração da variável nobre
while (count < topPrime) {
boolean prime = true;
dentro do ciclo tornam ineficientes? (Suponho que isso não importa, desde que eu pensaria Java seria otimizar esse)
boolean prime;
while (count < topPrime) {
prime = true;
C #
Enhancement para de Aistina código :
Isso faz uso do fato de que todos os números primos maiores que 3 são da forma 6n + 1 ou 6n -. 1
Esta foi de cerca de um aumento de velocidade de 4-5% sobre incrementando por um para cada passagem através do laço.
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;
}
}
A minha opinião a otimização, evitando truques muito enigmáticas. Eu uso o truque dada pela I-DÊ-TERRÍVEL, o conselho, que eu sabia e esqueceu ...: -)
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();
}
}
Sim, eu usei um rotulados continuar, primeira vez que eu experimentá-los em Java ...
Eu sei que eu pule cálculo dos primeiros números primos, mas eles são bem conhecidos, nenhum ponto para recalcular-los. :-) eu posso codificar a sua saída, se necessário! Ao lado, ele não lhe dá uma vantagem decisiva de qualquer maneira.
Resultado:
- Primeiro
Última privilegiada = 2015201
O tempo total = 4.281
- Segundo
Última privilegiada = 2015201
O tempo total = 0,953
Não é mau. Pode ser melhorado um pouco, suponho, mas muito otimização pode matar bom código.
Você deve ser capaz de fazer o loop interno duas vezes mais rápido, avaliando única os números ímpares. Não sei se isso é válido Java, eu estou acostumado a C ++, mas eu tenho certeza que ele pode ser adaptado.
if (current != 2 && current % 2 == 0)
prime = false;
else {
for (int i = 3; i < top; i+=2) {
if (current % i == 0) {
prime = false;
break;
}
}
}
Eu decidi tentar isso em F #, minha primeira tentativa decente para ele. Usando o Crivo de Eratóstenes no meu 2.2GHz Core 2 Duo ele é executado através 2..150,000 em cerca de 200 milissegundos. Cada vez que ele chama de auto é eliminado os múltiplos atuais da lista, por isso só fica mais rápido como ele vai junto. Esta é uma das minhas primeiras tentativas em F # para quaisquer comentários construtivos seria apreciada.
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
Eu aposto Miller-Rabin seria mais rápido. Se você testar números contíguos suficientes torna-se determinista, mas eu não me preocupei. Uma vez que um algoritmo aleatório atinge o ponto em que a sua taxa de falha é igual à probabilidade de que um soluço CPU irá causar um resultado errado, ele simplesmente não importa mais.
Aqui está a minha solução ... é bastante rápido ... ele calcula os números primos entre 1 e 10 milhões em 3 segundos em minha máquina (core i7 @ 2.93GHz) em Vista64.
A minha solução é em C, mas eu não sou um programador C profissional. Sinta-se livre para criticar o algoritmo e o próprio código:)
#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;
}
Aqui está minha opinião sobre ele. O programa é writtern em C e leva 50 milissegundos no meu laptop (Core 2 Duo, 1 GB de RAM). Eu estou mantendo todos os números primos calculados em uma matriz e tentando divisibilidade apenas até sqrt de número. Claro, isso não funciona quando precisamos número muito grande de números primos (tentei com 100000000) como uma matriz cresce muito grande e dá culpa seg.
/*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
@ Mark Ransom - não sei se isso é java de código
Eles vão lamentar possivelmente , mas eu queria reescrever utilizando o paradigma aprendi a confiança em Java e eles disseram para ter algum divertimento, certifique-se de que eles entendem que especificação diz nada que os efeitos encomendar na retornado conjunto de resultados, você também lançaria valores conjunto de resultados de pontos () para um tipo de lista dada a minha one-off no bloco de notas antes de tomar um curto recado
=============== começar código não testado ===============
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 ....
}
=============== código não testado final ===============
Utilizando Conjuntos de hash permite pesquisar resultados como B-árvores, assim, os resultados podiam ser empilhadas até que a máquina começa a falhar, então, que o ponto de partida poderia ser utilizado para um outro bloco de teste == o fim de um prazo usado como um valor Construtor para outra corrida, persistindo ao trabalho disco já realizado e permitindo designs feed-forward incrementais. Queimado para fora agora, a lógica de loop análise de necessidades.
patch (além de adicionar 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
Eu encontrei isso em algum lugar do código na minha máquina quando comecei a ler esta entrada blog sobre números primos. O código é em C # e o algoritmo que eu usei veio da minha cabeça, embora seja provavelmente em algum lugar na Wikipedia. ;) De qualquer forma, ele pode buscar os primeiros 150000 números primos em cerca de 300ms. Descobri que a soma dos números ímpares primeiro n é igual a n ^ 2. Novamente, não é provavelmente uma prova disso em algum lugar na wikipedia. Então, sabendo disso, eu posso escrever um algoritmo que wil nunca tem que calcular uma raiz quadrada, mas eu tenho que calcular de forma incremental para encontrar os primos. Então, se você quer que o primeiro-Nth, este algo terá de encontrar as (n-1) anteriores primos antes! Então é isso. Divirta-se!
//
// 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;
}
Aqui está a minha contribuição:
Máquina: 2,4 GHz Quad-Core i7 w / 8GB de RAM @ 1600MHz
Compiler: clang++ main.cpp -O3
Benchmarks:
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$
Fonte:
#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;
}
Isto usa o Sieve de abordagem Erastothenes, eu otimizado tanto quanto eu posso com meu conhecimento. Melhorias bem-vindas.
