رئيس الوزراء رقم حساب المتعة
https://stackoverflow.com/questions/288200
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
لدينا قليلا من المرح هنا في العمل.بدأ كل شيء مع واحد من الرجال إنشاء Hackintosh وكنا نتسائل ما إذا كانت أسرع من ويندوز مربع (تقريبا) نفس المواصفات التي لدينا.لذلك قررنا كتابة اختبار قليلا عن ذلك.مجرد عدد الوزراء آلة حاسبة.هو مكتوب في جاوة يخبرنا الوقت المستغرق في حساب أول ن الأعداد الأولية.
محسن النسخة أدناه - الآن يأخذ ~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 شيء وهي مجرد وجود بعض المرح مع تحسين ذلك.أول محاولة مع أي تحقيق أمثلية (رمز أعلاه زوجين) ركض حوالي 52.6 دقيقة للعثور على أول 150000 الأعداد الأولية.هذا التحسين هو يركض 47.2 دقيقة.
إذا كنت تريد أن يكون الذهاب و نشر النتائج الخاصة بك ، ثم عصا م.
مواصفات الكمبيوتر أنا على التوالي على هي Pentium D 2.8 GHz, 2GB RAM, تشغيل أوبونتو 8.04.
أفضل الأمثل حتى الآن الجذر التربيعي الحالي ، ذكر لأول مرة من قبل جيسون 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;
ذلك أن الأمور الكثير جدا.
تحرير:
المزيد من التحسين من باب المجاملة جو بينيدا:
إزالة المتغير "أعلى".
int count = 1;
...
for (int i = 3; i*i <= current; i += 2)
...
current += 2;
إذا كان ذلك الأمثل في الواقع يزيد من سرعة تصل إلى جاوة.
حساب الجذر التربيعي يأخذ الكثير من الوقت بالمقارنة مع ضرب رقمين.ومع ذلك منذ ننتقل الضرب في حلقة هذا يتم في كل حلقة.لذلك هذا يمكن أن تبطئ الأشياء اعتمادا على كيفية بسرعة الجذر التربيعي الخوارزمية في جافا.
نصائح أخرى
هذا هو أسوأ قليلا من غربال هل على 8 ميغاهيرتز 8088 في توربو باسكال في عام 1986 أو نحو ذلك.لكن ذلك كان بعد أمثلية :)
منذ كنت تبحث عن لهم في ترتيب تصاعدي ، يمكن أن نضع قائمة يعبي كنت قد وجدت بالفعل فقط تحقق القسمة ضدهم ، لأن كل غير الأعداد يمكن أن تخفض إلى قائمة من أقل العوامل الرئيسية.مع أن الجمع بين نصيحة السابقة حول عدم التحقق من العوامل الجذر التربيعي العدد الحالي ، عليك نفسك الرتق كفاءة التنفيذ.
هنا هو سريعة وبسيطة الحل:
- إيجاد يعبي اقل من 100000;9592 تم العثور عليها في 5 ms
- إيجاد يعبي اقل من 1000000;78498 تم العثور عليها في 20 ms
- إيجاد يعبي اقل من 10000000;664579 وجدت في 143 ms
- إيجاد يعبي اقل من 100000000;5761455 وجدت في 2024 ms
إيجاد يعبي اقل من 1000000000;50847534 وجدت في 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(); }
يستغرق أقل من ثانية (2.4 GHz) لتوليد أول 150000 الأعداد في بيثون باستخدام غربال إراتوستينس:
#!/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;
ضمن حلقة جعلها غير فعالة?(أفترض أنه لا يهم لأن أعتقد جافا تحسين هذا)
boolean prime;
while (count < topPrime) {
prime = true;
C#
تعزيز Aistina كود:
وهذا يجعل استخدام من حقيقة أن جميع يعبي أكبر من 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();
}
}
نعم أنا استخدم المسمى مواصلة أول مرة أحاول في جافا...
أنا أعرف تخطي حساب القليلة الأولى يعبي, ولكن من المعروف جيدا أنها لا تشير إلى حساب لهم.:-) أنا يمكن أن الثابت رمز إنتاجها إذا لزم الأمر!إلى جانب أنها لا تعطي ميزة حاسمة على أي حال.
النتائج:
- أولا
الماضي رئيس الوزراء = 2015201
الزمن الكلي = 4.281
-- الثانية
الماضي رئيس الوزراء = 2015201
الزمن الكلي = 0.953
ليس سيئا.قد تحسنت قليلا, أعتقد, ولكن الكثير من التحسين يمكن أن تقتل كود جيدة.
يجب أن تكون قادرة على جعل الحلقة الداخلية أسرع مرتين من قبل فقط تقييم الأعداد الفردية.لست متأكدا إذا كان هذا هو صالح جافا, أنا استخدم 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 Ghz 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.93 Ghz) على Vista64.
الحل هو في 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;
}
هنا هو بلدي يأخذ على ذلك.البرنامج هو writtern في ج ويأخذ 50 ميلي ثانية على جهاز الكمبيوتر المحمول(Core 2 Duo, 1 جيجابايت من ذاكرة الوصول العشوائي).أنا أحفظ كل حساب يعبي في مجموعة ومحاولة القسمة فقط حتى الجذر التربيعي من عدد.بالطبع, هذا لا يعمل عندما نحتاج إلى عدد كبير جدا من يعبي(حاولت مع 100000000) مجموعة كما ينمو كبيرة جدا ويعطي 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
@ مارك الفدية ، لست متأكدا إذا كان هذا هو كود جافا
وسوف أنين ربما ولكن كنت ترغب في إعادة كتابة باستخدام نموذج تعلمت أن الثقة في جافا و قالوا الحصول على بعض المتعة ، يرجى التأكد من أنهم يفهمون أن المواصفات لا يقول شيئا أن الآثار الطلب على إرجاع مجموعة نتائج ، كما أن يلقي نتيجة تعيين نقطة قيم() إلى قائمة نوع معين بلدي لمرة واحدة في المفكرة قبل اتخاذ مأمورية قصيرة
=============== تبدأ تختبر رمز ===============
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 ....
}
=============== نهاية لم تختبر رمز ===============
باستخدام تجزئة مجموعات يسمح نتائج البحث ب-الأشجار ، وبالتالي فإن النتائج يمكن أن تكون مكدسة حتى الجهاز يبدأ تفشل ثم أن نقطة انطلاق يمكن أن تستخدم في كتلة أخرى من الاختبار == نهاية تشغيل تستخدم منشئ قيمة آخر تشغيل المستمرة إلى القرص بالعمل الذي أنجز والسماح الأعلاف الإضافية إلى الأمام التصاميم.محترقة الآن حلقة المنطق تحليل الاحتياجات.
التصحيح (بالإضافة إلى إضافة الجذر التربيعي) :
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 الأعداد في 300ms.اكتشفت أن مجموع ن أول الأعداد الفردية يساوي n^2.مرة أخرى, ربما هناك دليل على ذلك في مكان ما على ويكيبيديا.حتى يعرف هذا, أستطيع أن أكتب خوارزمية فيل أبدا لحساب الجذر التربيعي ولكن علي حساب تدريجيا لإيجاد الأعداد الأولية.حتى إذا كنت تريد أقصى الوزراء ، algo سوف تضطر إلى العثور على (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.4 GHz Quad-Core 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 النهج ، لقد محسن بقدر ما أستطيع مع معرفتي.تحسينات موضع ترحيب.
