https://stackoverflow.com/questions/288200
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
우리는 직장에서 약간의 재미를 가지고 있습니다. 그것은 모두 Hackintosh를 설정하는 사람들 중 하나로 시작했으며 우리는 그것이 우리가 가진 것과 거의 같은 사양의 Windows 상자보다 빠른지 궁금했습니다. 그래서 우리는 그것에 대해 약간의 테스트를 작성하기로 결정했습니다. 간단한 소수 계산기. 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);
}
}
우리는 전체 Hackintosh vs PC의 줄거리를 거의 잃어 버렸고 최적화하는 데 재미를 느끼고 있습니다. 최적화가없는 첫 번째 시도 (위의 코드에는 커플이 있습니다)는 최초의 150000 소수를 찾기 위해 약 52.6 분 정도 실행되었습니다. 이 최적화는 약 47.2 분 정도 실행됩니다.
가서 결과를 게시하려면 EM을 고수하십시오.
실행중인 PC의 사양은 펜티엄 D 2.8GHz, 2GB RAM, Ubuntu 8.04를 실행합니다.
지금까지 최고의 최적화는 Jason Z.가 처음 언급 한 현재의 제곱근이었습니다.
해결책
글쎄, 나는 몇 가지 빠른 최적화를 볼 수 있습니다. 먼저 각 번호를 현재 번호의 절반까지 시도 할 필요가 없습니다.
대신 현재 숫자의 제곱근까지만 시도해보십시오.
그리고 다른 최적화는 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;
이것은 속도가 상당히 높아야합니다.
편집하다:
Joe Pineda의 최적화 제공 :
변수 "상단"을 제거하십시오.
int count = 1;
...
for (int i = 3; i*i <= current; i += 2)
...
current += 2;
이 최적화가 실제로 증가하면 속도가 증가하면 Java가 있습니다.
제곱근을 계산하는 데는 두 숫자를 곱하는 것과 비교하여 많은 시간이 걸립니다. 그러나 곱셈을 for 루프로 옮기기 때문에 모든 단일 루프가 이루어집니다. 따라서 이것은 Java의 제곱근 알고리즘이 얼마나 빨리 있는지에 따라 속도를 늦출 수 있습니다.
다른 팁
1986 년 Turbo Pascal에서 8MHz 8088에서 내 체가 한 것보다 조금 더 나쁩니다. 그러나 그것은 최적화 이후였습니다 :)
오름차순 순서로 검색하고 있기 때문에 이미 찾은 프라임 목록을 유지하고 모든 비 프라임 번호가 더 적은 주요 요인 목록으로 축소 될 수 있기 때문에 이에 대한 분할 만 확인할 수 있습니다. 현재 숫자의 제곱근에있는 요소를 확인하지 않는 것에 대한 이전 팁과 결합하면 매우 대담한 효율적인 구현이 될 것입니다.
다음은 빠르고 간단한 솔루션입니다.
- 100000 미만의 프라임 찾기; 9592는 5ms에서 발견되었다
- 1000000 미만의 프라임 찾기; 78498은 20ms에서 발견되었습니다
- 10000000 미만의 프라임 찾기; 664579는 143ms에서 발견되었습니다
- 100000000 미만의 프라임 찾기; 5761455는 2024 년에 발견되었습니다
1000000000 미만의 프라임 찾기; 50847534는 23839ms에서 발견되었습니다
//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(); }
Eratosthenes의 체를 사용하여 Python에서 처음 150000 소수를 생성하는 데 1 초 (2.4GHz) 미만이 필요합니다.
#!/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]
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;
}
}
산출:
총 시간 : 2.087 초
프라임을 찾는 더 좋은 방법이 있다는 점을 명심하십시오 ...
이 루프를 취할 수 있다고 생각합니다.
for (int i = 2; i < top; i++)
그리고 당신의 카운터 변수가 3에서 나오고 홀수로 모드를 수행하려고 시도합니다. 2 이외의 모든 프라임은 짝수 숫자로 나눌 수 없기 때문입니다.
가변 프라임의 재배치를 수행합니다
while (count < topPrime) {
boolean prime = true;
루프 내에서 비효율적입니까? (Java가 이것을 최적화 할 것이라고 생각하기 때문에 중요하지 않다고 생각합니다)
boolean prime;
while (count < topPrime) {
prime = true;
씨#
향상 Aistina의 코드:
이것은 3보다 큰 모든 프라임이 형태 6n + 1 또는 6n -1이라는 사실을 사용합니다.
이것은 루프를 통과하는 모든 패스에 대해 1 증가한 약 4-5%의 속도 증가였습니다.
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;
}
}
너무 비밀스러운 속임수를 피하면서 최적화를 취합니다. 나는 I-Give-Terible-Advice가 제공 한 트릭을 사용합니다.
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.2GHz 코어 2 듀오에서 Eratosthenes의 체를 사용하여 약 200 밀리 초에서 2..150,000을 통과합니다. 자체라고 부를 때마다 목록에서 현재 배수를 제거하므로 진행됨에 따라 점점 더 빨라집니다. 이것은 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
Miller-Rabin이 더 빠를 것이라고 확신합니다. 충분히 인접한 숫자를 테스트하면 결정 론적이지만 나는 신경 쓰지 않을 것입니다. 무작위 알고리즘이 실패율이 CPU 딸꾹질이 잘못된 결과를 초래할 가능성과 동일하다는 점에 도달하면 더 이상 중요하지 않습니다.
내 솔루션은 다음과 같습니다. 상당히 빠릅니다 ... Vista64의 컴퓨터 (Core i7 @ 2.93GHz)에서 3 초 동안 1 ~ 10,000,000 사이의 프라임을 계산합니다.
내 솔루션은 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의 Writtern이며 내 랩탑에서 50 밀리 초를 섭취합니다 (Core 2 Duo, 1GB RAM). 계산 된 모든 프라임을 배열에 보관하고 SQRT까지만 분할을 시도합니다. 물론, 이것은 배열이 너무 커지고 Seg 결함을주기 때문에 매우 많은 수의 프라임 (10000000으로 시도)이 필요할 때 작동하지 않습니다.
/*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- 이것이 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#에 있고 내가 사용한 알고리즘은 아마도 Wikipedia 어딘가에 있지만 내 머리에서 나왔습니다. ;) 어쨌든, 그것은 약 300ms에서 처음 150000 소수를 가져올 수 있습니다. 나는 첫 번째 홀수 숫자의 합이 n^2와 같다는 것을 발견했다. 다시 말하지만, 아마도 Wikipedia 어딘가에 이것에 대한 증거가있을 것입니다. 따라서 이것을 알면 제곱근을 계산할 필요가없는 알고리즘을 쓸 수 있지만 프라임을 찾으려면 점진적으로 계산해야합니다. 따라서 Nth Prime을 원한다면이 알고리는 이전의 프라임 (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;
}
내 기여는 다음과 같습니다.
기계 : 2.4GHz 쿼드 코어 i7 w/ 8GB RAM @ 1600MHz
컴파일러: 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;
}
이것은 Erastothenes 접근법의 체를 사용합니다. 나는 내 지식으로 가능한 한 최적화했습니다. 개선을 환영합니다.
제휴하지 않습니다 StackOverflow
