usando - numeros primos en java con while
Diversión de cálculo de números primos (18)
Apuesto a que Miller-Rabin sería más rápido. Si prueba suficientes números contiguos se vuelve determinista, pero ni siquiera me molestaría. Una vez que un algoritmo aleatorizado llega al punto en que su tasa de fallas es igual a la probabilidad de que un problema en la CPU cause un resultado incorrecto, ya no importa.
Estamos teniendo un poco de diversión aquí en el trabajo. Todo comenzó con uno de los muchachos configurando un Hackintosh y nos preguntábamos si era más rápido que un Windows Box de (casi) las mismas especificaciones que tenemos. Así que decidimos escribir una pequeña prueba para ello. Solo una simple calculadora de números Prime. Está escrito en Java y nos dice el tiempo que lleva calcular los primeros n números principales.
La versión optimizada a continuación: ahora demora ~ 6,6 segundos
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);
}
}
Hemos perdido la trama de todo el Hackintosh vs PC y estamos divirtiéndonos con la optimización. Primer intento sin optimizaciones (el código anterior tiene un par) corrió alrededor de 52.6min para encontrar los primeros 150000 números primos. Esta optimización se ejecuta alrededor de 47.2 minutos.
Si quieres probar y publicar tus resultados, entonces pégalo.
Las especificaciones para PC en las que lo ejecuto son Pentium D 2.8GHz, 2GB RAM, ejecutando Ubuntu 8.04.
La mejor optimización hasta el momento ha sido la raíz cuadrada de la corriente, mencionada por primera vez por Jason Z.
Decidí probar esto en F #, mi primer intento decente. Usando el Tamiz de Eratóstenes en mi 2.2Ghz Core 2 Duo corre a través de 2..150,000 en aproximadamente 200 milisegundos. Cada vez que se llama a sí mismo, elimina los múltiplos actuales de la lista, por lo que se vuelve más rápido a medida que avanza. Este es uno de mis primeros intentos en F # por lo que cualquier comentario constructivo sería apreciado.
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
¿La re-declaración de la variable prima
while (count < topPrime) {
boolean prime = true;
dentro del ciclo lo hacen ineficiente? (Supongo que no importa, ya que creo que Java optimizaría esto)
boolean prime;
while (count < topPrime) {
prime = true;
Bueno, veo un par de optimizaciones rápidas que se pueden hacer. Primero, no tiene que probar cada número hasta la mitad del número actual.
En cambio, solo has intentado hasta la raíz cuadrada del número actual.
Y la otra optimización fue lo que dijo BP con un giro: en lugar de
int count = 0;
...
for (int i = 2; i < top; i++)
...
if (current == 2)
current++;
else
current += 2;
utilizar
int count = 1;
...
for (int i = 3; i < top; i += 2)
...
current += 2;
Esto debería acelerar las cosas bastante.
EDITAR:
Más optimización cortesía de Joe Pineda:
Retire la variable "arriba".
int count = 1;
...
for (int i = 3; i*i <= current; i += 2)
...
current += 2;
Si esta optimización aumenta la velocidad, es hasta java.
Calcular la raíz cuadrada requiere mucho tiempo en comparación con la multiplicación de dos números. Sin embargo, dado que movemos la multiplicación en el ciclo for, esto se realiza en cada bucle. Así que esto PODRÍA ralentizar las cosas dependiendo de qué tan rápido sea el algoritmo de raíz cuadrada en java.
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;
}
}
Salida:
Tiempo total tomado: 2.087 segundos
Dado que los está buscando en orden ascendente, puede mantener una lista de los números primos que ya ha encontrado y solo verificar la divisibilidad con respecto a ellos, ya que todos los números no primos se pueden reducir a una lista de factores primos menores. Combine eso con el consejo anterior sobre no verificar los factores sobre la raíz cuadrada del número actual, y usted tendrá una implementación muy eficiente.
Debería poder hacer que el bucle interno sea dos veces más rápido al solo evaluar los números impares. No estoy seguro si esto es válido Java, estoy acostumbrado a C ++, pero estoy seguro de que se puede adaptar.
if (current != 2 && current % 2 == 0)
prime = false;
else {
for (int i = 3; i < top; i+=2) {
if (current % i == 0) {
prime = false;
break;
}
}
}
Eso es un poco peor de lo que mi tamiz hizo en 8 Mhz 8088 en turbo pascal en 1986 más o menos. Pero eso fue después de las optimizaciones :)
Mi toma en la optimización, evitando trucos demasiado crípticos. Utilizo el truco dado por I-GIVE-TERRIBLE-ADVICE, que sabía y olvidé ... :-)
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();
}
}
Sí, utilicé una etiqueta de continuar, la primera vez que los pruebo en Java ...
Sé que omito el cálculo de los primeros números primos, pero son bien conocidos, no tiene sentido recalcularlos. :-) ¡Puedo codificar su salida si es necesario! Además, no da una ventaja decisiva de todos modos.
Resultados:
-- Primero
Última prima = 2015201
Tiempo total = 4.281
-- Segundo
Última prima = 2015201
Tiempo total = 0.953
No está mal. Se podría mejorar un poco, supongo, pero demasiada optimización puede matar a un buen código.
Teniendo en cuenta que hay mejores formas de buscar primos ...
Creo que puedes tomar este ciclo:
for (int i = 2; i < top; i++)
y haga que su contra variable I vaya desde 3 y solo intente hacer la modificación en números impares, ya que todos los números primos distintos de 2 nunca son divisibles por números pares.
Nos lleva menos de un segundo (2.4GHz) generar los primeros 150000 números primos en Python usando Sieve of Eratosthenes:
#!/usr/bin/env python
def iprimes_upto(limit):
"""Generate all prime numbers less then limit.
http://.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]))
Ejemplo:
$ 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]
Esta es mi solución ... es bastante rápido ... calcula los números primos entre 1 y 10,000,000 en 3 segundos en mi máquina (core i7 @ 2.93Ghz) en Vista64.
Mi solución está en C, pero no soy un programador de C profesional. No dude en criticar el algoritmo y el código en sí :)
#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;
}
@ Mark Ransom - no estoy seguro si esto es código Java
Ellos gemirán posiblemente pero yo deseé reescribir usando un paradigma en el que aprendí a confiar en Java y dijeron que se divirtieran, por favor asegúrense de que entiendan que la especificación no dice nada que los efectos ordenen en el conjunto de resultados devuelto, también arrojarían el conjunto de resultados dot values () a un tipo de lista dado mi único en el Bloc de notas antes de tomar un pequeño encargo
=============== comience el código no probado ===============
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 ....
}
=============== fin del código no probado ===============
El uso de Hash Sets permite buscar resultados como B-Trees, por lo que los resultados pueden apilarse hasta que la máquina comience a fallar, entonces ese punto de inicio podría usarse para otro bloque de pruebas == al final de una ejecución utilizado como valor de Constructor para otra ejecución , persistiendo en el trabajo del disco ya realizado y permitiendo diseños incrementales de avance. Quemado en este momento, la lógica de bucle necesita análisis.
parche (más agregar 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 Error(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.Error soe)
{
// Might happen
System.out.println(soe.getMessage());//
return;
}
}
}// end class Alice
Aquí está mi opinión sobre esto. El programa está escrito en C y tarda 50 milisegundos en mi computadora portátil (Core 2 Duo, 1 GB Ram). Mantengo todos los primos calculados en una matriz e intento de divisibilidad solo hasta sqrt de número. Por supuesto, esto no funciona cuando necesitamos una gran cantidad de primos (probados con 100000000) ya que la matriz crece demasiado grande y da un fallo 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
Encontré este código en algún lugar de mi máquina cuando comencé a leer esta entrada de blog sobre números primos. El código está en C # y el algoritmo que utilicé salió de mi cabeza, aunque probablemente esté en alguna parte de Wikipedia. ;) De todos modos, puede obtener los primeros 150000 números primos en aproximadamente 300ms. Descubrí que la suma de los n primeros números impares es igual a n ^ 2. De nuevo, probablemente haya una prueba de esto en algún lugar de la wikipedia. Entonces, sabiendo esto, puedo escribir un algoritmo que nunca tendrá que calcular una raíz cuadrada, pero tengo que calcular incrementalmente para encontrar los primos. Por lo tanto, si desea la N-ésima primo, ¡este algo tendrá que encontrar los primos precedentes (N-1) anteriormente! Entonces ahí está. ¡Disfrutar!
//
// 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;
}
Aquí hay una solución rápida y simple:
- Encontrar números primos inferiores a 100000; 9592 fueron encontrados en 5 ms
- Encontrar números primos inferiores a 1000000; 78498 fueron encontrados en 20 ms
- Encontrar números primos inferiores a 10000000; 664579 fueron encontrados en 143 ms
- Encontrar números primos inferiores a 100000000; 5761455 fueron encontrados en 2024 ms
Encontrar números primos inferiores a 1000000000; 50847534 fueron encontrados en 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(); }
Aquí está mi contribución:
Máquina: 2.4GHz Quad-Core i7 w / 8GB RAM a 1600MHz
Compilador: clang++ main.cpp -O3
Puntos de referencia:
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$
Fuente:
#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;
}
Esto utiliza el enfoque de Sieve of Erastothenes, lo he optimizado tanto como puedo con mi conocimiento. Mejoras bienvenidas.
DO#
Mejora al código de Aistina :
Esto hace uso del hecho de que todos los números primos mayores que 3 son de la forma 6n + 1 o 6n - 1.
Esto fue aproximadamente un aumento de velocidad del 4-5% sobre el incremento en 1 por cada pasada a través del ciclo.
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;
}
}