最初の 10000 個の素数を出力したい。誰でもこれに最も効率的なコードを教えてもらえますか? 説明:
- n >10000 でコードが効率的でないかどうかは問題ではありません。
- コードのサイズは問いません。
- どのような方法でも値をハードコーディングすることはできません。
Niyaz
質問する
69235 次
30 に答える
39
エラトステネスのふるいまたはアトキンのふるいのいずれかのふるいをお勧めします。
ふるいまたはエラトステネスは、おそらく素数のリストを見つける最も直感的な方法です。基本的にあなた：
- 2 から任意の制限までの数のリストを書き留めます。たとえば、1000 としましょう。
- 消されていない最初の数 (最初の反復ではこれは 2) を取り、リストからその数のすべての倍数を消します。
- リストの最後に到達するまで、手順 2 を繰り返します。消されていない数字はすべて素数です。
明らかに、このアルゴリズムの動作を高速化するために実行できる最適化は多数ありますが、これが基本的な考え方です。
Atkin のふるいも同様のアプローチを使用していますが、残念ながら私はそれについて説明するのに十分な知識がありません. しかし、私がリンクしたアルゴリズムは、古代の Pentium II-350 で 1000000000 までのすべての素数を計算するのに 8 秒かかることを知っています。
エラトステネスのふるいソース コード: http://web.archive.org/web/20140705111241/http://primes.utm.edu/links/programs/sieves/Eratosthenes/C_source_code/
Atkin ソース コードのふるい: http://cr.yp.to/primegen.html
于 2008-08-05T23:49:43.963 に答える
20
これは、ハードコーディングの制限に厳密に違反しているわけではありませんが、非常に近いものです。代わりに、このリストをプログラムでダウンロードして印刷してみませんか?
于 2008-08-31T22:20:44.647 に答える
13
Haskellでは、エラトステネスのふるいの数学的定義をほぼ一言一句書き留めることができます。
import Data.List.Ordered (minus, union)
primes = 2 : minus [3..] (foldr (\p r -> p*p : union [p*p+p, p*p+2*p..] r)
[] primes)
primes !! 10000ほぼ瞬時です。
参照：
上記のコードは、オッズのみで動作するように簡単に調整できprimes = 2 : 3 : minus [5,7..] (foldr (\p r -> p*p : union [p*p+2*p, p*p+4*p..] r) [] (tail primes))ます。時間の複雑さは、ツリーのような構造に折りたたむことによって大幅に改善され（最適値をほぼ対数係数上に）、空間の複雑さは、多段階の素数生成によって大幅に改善されます。
primes = 2 : _Y ( (3:) . sieve 5 . _U . map (\p -> [p*p, p*p+2*p..]) )
where
_Y g = g (_Y g) -- non-sharing fixpoint combinator
_U ((x:xs):t) = x : (union xs . _U . pairs) t -- ~= nub.sort.concat
pairs (xs:ys:t) = union xs ys : pairs t
sieve k s@(x:xs) | k < x = k : sieve (k+2) s -- ~= [k,k+2..]\\s,
| otherwise = sieve (k+2) xs -- when s⊂[k,k+2..]
（Haskellでは、括弧はグループ化に使用され、関数呼び出しは並置によって示され、リスト(:)の短所(.)演算子であり、関数合成演算子です:) (f . g) x = (\y -> f (g y)) x = f (g x)。
于 2012-04-24T16:30:15.850 に答える
13
GateKiller、ループ内に abreakを追加するのはどうですか? 6 が 2 で割り切れる場合は、3 と 5 をチェックする必要がないため、処理が大幅に高速化されます。ifforeach
ArrayList primeNumbers = new ArrayList();
for(int i = 2; primeNumbers.Count < 10000; i++) {
bool divisible = false;
foreach(int number in primeNumbers) {
if(i % number == 0) {
divisible = true;
break;
}
}
if(divisible == false) {
primeNumbers.Add(i);
Console.Write(i + " ");
}
}
于 2008-08-27T20:26:27.947 に答える
11
@マット: log(log(10000)) は ~2
ウィキペディアの記事から（あなたが引用した）Sieve of Atkin：
このふるいは、N 1/2+o(1)ビットのメモリ
O(N/log log N)のみを使用して演算を使用して、N までの素数を計算します。これは、 演算と O(N 1/2 (log log N)/log N) ビットのメモリ(AOL Atkin、DJ Bernstein、2004)を使用する Eratosthenes のふるいよりも少し優れています。これらの漸近的な計算の複雑さには、車輪の因数分解などの単純な最適化や、計算をより小さなブロックに分割することが含まれます。O(N)
O(N)(Eratosthenes の場合) および(Atkin の場合)に沿った漸近的な計算の複雑さを考えると、実装された場合にどのアルゴリズムがより高速になるかO(N/log(log(N)))(small の場合) は言えません。N=10_000
アヒム・フラメンカンプは『エラトステネスのふるい』の中で次のように書いています。
によって引用：
@数値1
約 10^9 より大きい間隔の場合、確かに 10^10 より大きい場合、エラトステネスのふるいは、既約バイナリ二次形式を使用するアトキンスとバーンスタインのふるいよりも優れています。背景情報については、彼らの論文と W. Galway の Ph.D. の段落 5 を参照してください。論文。
したがって10_000、エラトステネスのふるいは、アトキンのふるいよりも高速になります。
OPに答えるコードはprime_sieve.cです（引用num1）
于 2008-10-06T20:03:30.423 に答える
10
GMP を使用すると、次のように記述できます。
#include <stdio.h>
#include <gmp.h>
int main() {
mpz_t prime;
mpz_init(prime);
mpz_set_ui(prime, 1);
int i;
char* num = malloc(4000);
for(i=0; i<10000; i++) {
mpz_nextprime(prime, prime);
printf("%s, ", mpz_get_str(NULL,10,prime));
}
}
私の 2.33GHz Macbook Pro では、次のように実行されます。
time ./a.out > /dev/null
real 0m0.033s
user 0m0.029s
sys 0m0.003s
同じラップトップで 1,000,000 個の素数を計算する:
time ./a.out > /dev/null
real 0m14.824s
user 0m14.606s
sys 0m0.086s
GMP は、この種のことに対して高度に最適化されています。独自のアルゴリズムを作成してアルゴリズムを本当に理解したい場合を除き、C で libGMP を使用することをお勧めします。
于 2008-08-29T07:06:43.937 に答える
7
まったく効率的ではありませんが、正規表現を使用して素数をテストできます。
/^1?$|^(11+?)\1+$/
これは、 k個の「<code> 1」で構成される文字列の場合、kが素数ではないかどうかをテストします（つまり、文字列が1つの「<code>1」または任意の数の「<code>1」で構成されているかどうか）。n- ary積として表されます）。
于 2008-08-03T18:52:17.093 に答える
5
CodeProjectで見つかったコードを調整して、次を作成しました。
ArrayList primeNumbers = new ArrayList();
for(int i = 2; primeNumbers.Count < 10000; i++) {
bool divisible = false;
foreach(int number in primeNumbers) {
if(i % number == 0) {
divisible = true;
}
}
if(divisible == false) {
primeNumbers.Add(i);
Console.Write(i + " ");
}
}
ASP.NET サーバーでこれをテストすると、ルーチンの実行に約 1 分かかりました。
于 2008-08-05T19:55:17.557 に答える
4
エラトステネスのふるいは、そのシンプルさとスピードから、最適な方法です。Cでの私の実装
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
int main(void)
{
unsigned int lim, i, j;
printf("Find primes upto: ");
scanf("%d", &lim);
lim += 1;
bool *primes = calloc(lim, sizeof(bool));
unsigned int sqrtlim = sqrt(lim);
for (i = 2; i <= sqrtlim; i++)
if (!primes[i])
for (j = i * i; j < lim; j += i)
primes[j] = true;
printf("\nListing prime numbers between 2 and %d:\n\n", lim - 1);
for (i = 2; i < lim; i++)
if (!primes[i])
printf("%d\n", i);
return 0;
}
素数を検出するための CPU 時間 (Pentium デュアル コア E2140 1.6 GHz、シングル コアを使用)
~ リムの 4 秒 = 100,000,000
于 2008-08-20T23:45:54.110 に答える
3
これは、数日前に PowerShell で作成したエラトステネスのふるいです。返される素数の数を識別するためのパラメーターがあります。
#
# generate a list of primes up to a specific target using a sieve of eratosthenes
#
function getPrimes { #sieve of eratosthenes, http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
param ($target,$count = 0)
$sieveBound = [math]::ceiling(( $target - 1 ) / 2) #not storing evens so count is lower than $target
$sieve = @($false) * $sieveBound
$crossLimit = [math]::ceiling(( [math]::sqrt($target) - 1 ) / 2)
for ($i = 1; $i -le $crossLimit; $i ++) {
if ($sieve[$i] -eq $false) {
$prime = 2 * $i + 1
write-debug "Found: $prime"
for ($x = 2 * $i * ( $i + 1 ); $x -lt $sieveBound; $x += 2 * $i + 1) {
$sieve[$x] = $true
}
}
}
$primes = @(2)
for ($i = 1; $i -le $sieveBound; $i ++) {
if($count -gt 0 -and $primes.length -ge $count) {
break;
}
if($sieve[$i] -eq $false) {
$prime = 2 * $i + 1
write-debug "Output: $prime"
$primes += $prime
}
}
return $primes
}
于 2009-09-07T18:52:12.030 に答える
2
Python で
import gmpy
p=1
for i in range(10000):
p=gmpy.next_prime(p)
print p
于 2010-02-22T07:45:46.507 に答える
2
ふるいは間違った答えのようです。ふるいは、最初の N 個の素数ではなく、数Nまでの素数を与えます。@Imran または @Andrew Szeto を実行すると、N までの素数が得られます。
結果セットの特定のサイズに達するまで、ますます大きな数値のふるいを試行し続け、既に取得した数値のキャッシュを使用する場合、ふるいはまだ使用できる可能性がありますが、@ Pat のようなソリューションよりもまだ高速ではないと思います.
于 2009-06-19T18:12:35.903 に答える
1
エラトステネスのふるいを使用すると、「広く知られている」素数アルゴリズムと比較して、計算がかなり高速になります。
wiki ( https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes ) の疑似コードを使用することで、C# で解決策を得ることができます。
/// Get non-negative prime numbers until n using Sieve of Eratosthenes.
public int[] GetPrimes(int n) {
if (n <= 1) {
return new int[] { };
}
var mark = new bool[n];
for(var i = 2; i < n; i++) {
mark[i] = true;
}
for (var i = 2; i < Math.Sqrt(n); i++) {
if (mark[i]) {
for (var j = (i * i); j < n; j += i) {
mark[j] = false;
}
}
}
var primes = new List<int>();
for(var i = 3; i < n; i++) {
if (mark[i]) {
primes.Add(i);
}
}
return primes.ToArray();
}
GetPrimes(100000000) には 2 秒と 330 ミリ秒かかります。
注: 値は、ハードウェアの仕様によって異なる場合があります。
于 2016-05-12T03:40:03.553 に答える
1
これは私のVB 2008コードで、仕事用のラップトップで1分27秒で10,000,000未満のすべての素数を見つけます。偶数をスキップし、テスト番号の sqrt より小さい素数のみを探します。0 からセンティナル値までの素数を見つけるようにのみ設計されています。
Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles
Button1.Click
Dim TestNum As Integer
Dim X As Integer
Dim Z As Integer
Dim TM As Single
Dim TS As Single
Dim TMS As Single
Dim UnPrime As Boolean
Dim Sentinal As Integer
Button1.Text = "Thinking"
Button1.Refresh()
Sentinal = Val(SentinalTxt.Text)
UnPrime = True
Primes(0) = 2
Primes(1) = 3
Z = 1
TM = TimeOfDay.Minute
TS = TimeOfDay.Second
TMS = TimeOfDay.Millisecond
For TestNum = 5 To Sentinal Step 2
Do While Primes(X) <> 0 And UnPrime And Primes(X) ^ 2 <= TestNum
If Int(TestNum / Primes(X)) - (TestNum / Primes(X)) = 0 Then
UnPrime = False
End If
X = X + 1
Loop
If UnPrime = True Then
X = X + 1
Z = Z + 1
Primes(Z) = TestNum
End If
UnPrime = True
X = 0
Next
Button1.Text = "Finished with " & Z
TM = TimeOfDay.Minute - TM
TS = TimeOfDay.Second - TS
TMS = TimeOfDay.Millisecond - TMS
ShowTime.Text = TM & ":" & TS & ":" & TMS
End Sub
于 2011-03-11T02:25:23.013 に答える
1
次の Mathcad コードは、最初の 100 万個の素数を 3 分未満で計算しました。
これはすべての数値に浮動小数点 double を使用し、基本的に解釈されることに注意してください。構文が明確であることを願っています。
于 2014-03-02T01:15:02.170 に答える
1
これは、私のラップトップで最初の 10,000 個の素数を 0.049655 秒で見つけ、最初の 1,000,000 個の素数を 6 秒未満で、最初の 2,000,000 個を 15 秒で見つける私のコードです
。このメソッドは、素数を見つけるために 2 つの手法を使用します
- まず第一に、素数以外の数は素数の倍数の複合体であるため、このコードは、テスト数を任意の数ではなくより小さい素数で割ることによってテストします。これにより、4 桁の数の場合は計算が少なくとも 10 倍減少し、より大きな数
- 次に、素数で割る以外に、テスト対象の数の根より小さいか等しい素数で除算するだけで、計算が大幅に削減されます。これは、数の根よりも大きい数には対応する数があるため、機能します。は数の根よりも小さくなければなりませんが、すでに根よりも小さいすべての数をテストしたため、テストされている数の根よりも大きい数を気にする必要はありません。
最初の 10,000 個の素数の出力例
https://drive.google.com/open?id=0B2QYXBiLI-lZMUpCNFhZeUphck0 https://drive.google.com/open?id=0B2QYXBiLI-lZbmRtTkZETnp6Ykk
これは C 言語のコードです。1 を入力してから 10,000 を入力して、最初の 10,000 個の素数を出力します。
編集:これには数学ライブラリが含まれていることを忘れていました。Windowsまたはビジュアルスタジオを使用している場合は問題ありませんが、Linuxでは-lm引数を使用してコードをコンパイルする必要があります。そうしないと、コードが機能しない可能性があります
例: gcc -Wall -o "%e " "%f" -lm
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <limits.h>
/* Finding prime numbers */
int main()
{
//pre-phase
char d,w;
int l,o;
printf(" 1. Find first n number of prime numbers or Find all prime numbers smaller than n ?\n"); // this question helps in setting the limits on m or n value i.e l or o
printf(" Enter 1 or 2 to get anwser of first or second question\n");
// decision making
do
{
printf(" -->");
scanf("%c",&d);
while ((w=getchar()) != '\n' && w != EOF);
if ( d == '1')
{
printf("\n 2. Enter the target no. of primes you will like to find from 3 to 2,000,000 range\n -->");
scanf("%10d",&l);
o=INT_MAX;
printf(" Here we go!\n\n");
break;
}
else if ( d == '2' )
{
printf("\n 2.Enter the limit under which to find prime numbers from 5 to 2,000,000 range\n -->");
scanf("%10d",&o);
l=o/log(o)*1.25;
printf(" Here we go!\n\n");
break;
}
else printf("\n Try again\n");
}while ( d != '1' || d != '2' );
clock_t start, end;
double cpu_time_used;
start = clock(); /* starting the clock for time keeping */
// main program starts here
int i,j,c,m,n; /* i ,j , c and m are all prime array 'p' variables and n is the number that is being tested */
int s,x;
int p[ l ]; /* p is the array for storing prime numbers and l sets the array size, l was initialized in pre-phase */
p[1]=2;
p[2]=3;
p[3]=5;
printf("%10dst:%10d\n%10dnd:%10d\n%10drd:%10d\n",1,p[1],2,p[2],3,p[3]); // first three prime are set
for ( i=4;i<=l;++i ) /* this loop sets all the prime numbers greater than 5 in the p array to 0 */
p[i]=0;
n=6; /* prime number testing begins with number 6 but this can lowered if you wish but you must remember to update other variables too */
s=sqrt(n); /* 's' does two things it stores the root value so that program does not have to calaculate it again and again and also it stores it in integer form instead of float*/
x=2; /* 'x' is the biggest prime number that is smaller or equal to root of the number 'n' being tested */
/* j ,x and c are related in this way, p[j] <= prime number x <= p[c] */
// the main loop begins here
for ( m=4,j=1,c=2; m<=l && n <= o;)
/* this condition checks if all the first 'l' numbers of primes are found or n does not exceed the set limit o */
{
// this will divide n by prime number in p[j] and tries to rule out non-primes
if ( n%p[j]==0 )
{
/* these steps execute if the number n is found to be non-prime */
++n; /* this increases n by 1 and therefore sets the next number 'n' to be tested */
s=sqrt(n); /* this calaulates and stores in 's' the new root of number 'n' */
if ( p[c] <= s && p[c] != x ) /* 'The Magic Setting' tests the next prime number candidate p[c] and if passed it updates the prime number x */
{
x=p[c];
++c;
}
j=1;
/* these steps sets the next number n to be tested and finds the next prime number x if possible for the new number 'n' and also resets j to 1 for the new cycle */
continue; /* and this restarts the loop for the new cycle */
}
// confirmation test for the prime number candidate n
else if ( n%p[j]!=0 && p[j]==x )
{
/* these steps execute if the number is found to be prime */
p[m]=n;
printf("%10dth:%10d\n",m,p[m]);
++n;
s = sqrt(n);
++m;
j=1;
/* these steps stores and prints the new prime number and moves the 'm' counter up and also sets the next number n to be tested and also resets j to 1 for the new cycle */
continue; /* and this restarts the loop */
/* the next number which will be a even and non-prime will trigger the magic setting in the next cycle and therfore we do not have to add another magic setting here*/
}
++j; /* increases p[j] to next prime number in the array for the next cycle testing of the number 'n' */
// if the cycle reaches this point that means the number 'n' was neither divisible by p[j] nor was it a prime number
// and therfore it will test the same number 'n' again in the next cycle with a bigger prime number
}
// the loops ends
printf(" All done !!\n");
end = clock();
cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
printf(" Time taken : %lf sec\n",cpu_time_used);
}
于 2017-05-06T11:48:38.673 に答える
0
多くの素数を計算するプログラムの作成に時間を費やしています。これは、最初の 1.000.000.000 個の素数を含むテキスト ファイルを計算するために使用したコードです。ドイツ語ですが、興味深いのはメソッドcalcPrimes()です。素数は Primzahlen という配列に格納されます。計算は 64 ビット整数を使用するため、64 ビット CPU をお勧めします。
import java.io.*;
class Primzahlengenerator {
long[] Primzahlen;
int LastUnknown = 2;
public static void main(String[] args) {
Primzahlengenerator Generator = new Primzahlengenerator();
switch(args.length) {
case 0: //Wenn keine Argumente übergeben worden:
Generator.printHelp(); //Hilfe ausgeben
return; //Durchfallen verhindern
case 1:
try {
Generator.Primzahlen = new long[Integer.decode(args[0]).intValue()];
}
catch (NumberFormatException e) {
System.out.println("Das erste Argument muss eine Zahl sein, und nicht als Wort z.B. \"Tausend\", sondern in Ziffern z.B. \"1000\" ausgedrückt werden.");//Hinweis, wie man die Argumente angeben muss ausgeben
Generator.printHelp(); //Generelle Hilfe ausgeben
return;
}
break;//dutchfallen verhindern
case 2:
switch (args[1]) {
case "-l":
System.out.println("Sie müsen auch eine Datei angeben!"); //Hilfemitteilung ausgeben
Generator.printHelp(); //Generelle Hilfe ausgeben
return;
}
break;//durchfallen verhindern
case 3:
try {
Generator.Primzahlen = new long[Integer.decode(args[0]).intValue()];
}
catch (NumberFormatException e) {
System.out.println("Das erste Argument muss eine Zahl sein, und nicht als Wort z.B. \"Tausend\", sondern in Ziffern z.B. \"1000\" ausgedrückt werden.");//Hinweis, wie man die Argumente angeben muss ausgeben
Generator.printHelp(); //Generelle Hilfe ausgeben
return;
}
switch(args[1]) {
case "-l":
Generator.loadFromFile(args[2]);//Datei Namens des Inhalts von Argument 3 lesen, falls Argument 2 = "-l" ist
break;
default:
Generator.printHelp();
break;
}
break;
default:
Generator.printHelp();
return;
}
Generator.calcPrims();
}
void printHelp() {
System.out.println("Sie müssen als erstes Argument angeben, die wieviel ersten Primzahlen sie berechnen wollen."); //Anleitung wie man das Programm mit Argumenten füttern muss
System.out.println("Als zweites Argument können sie \"-l\" wählen, worauf die Datei, aus der die Primzahlen geladen werden sollen,");
System.out.println("folgen muss. Sie muss genauso aufgebaut sein, wie eine Datei Primzahlen.txt, die durch den Aufruf \"java Primzahlengenerator 1000 > Primzahlen.txt\" entsteht.");
}
void loadFromFile(String File) {
// System.out.println("Lese Datei namens: \"" + File + "\"");
try{
int x = 0;
BufferedReader in = new BufferedReader(new FileReader(File));
String line;
while((line = in.readLine()) != null) {
Primzahlen[x] = new Long(line).longValue();
x++;
}
LastUnknown = x;
} catch(FileNotFoundException ex) {
System.out.println("Die angegebene Datei existiert nicht. Bitte geben sie eine existierende Datei an.");
} catch(IOException ex) {
System.err.println(ex);
} catch(ArrayIndexOutOfBoundsException ex) {
System.out.println("Die Datei enthält mehr Primzahlen als der reservierte Speicherbereich aufnehmen kann. Bitte geben sie als erstes Argument eine größere Zahl an,");
System.out.println("damit alle in der Datei enthaltenen Primzahlen aufgenommen werden können.");
}
/* for(long prim : Primzahlen) {
System.out.println("" + prim);
} */
//Hier soll code stehen, der von der Datei mit angegebenem Namen ( Wie diese aussieht einfach durch angeben von folgendem in cmd rausfinden:
//java Primzahlengenerator 1000 > 1000Primzahlen.txt
//da kommt ne textdatei, die die primzahlen enthält. mit Long.decode(String ziffern).longValue();
//erhält man das was an der entsprechenden stelle in das array soll. die erste zeile soll in [0] , die zweite zeile in [1] und so weiter.
//falls im arry der platz aus geht(die exception kenn ich grad nich, aber mach mal:
//int[] foo = { 1, 2, 3};
//int bar = foo[4];
//dann kriegst ne exception, das ist die gleiche die man kriegt, wenn im arry der platzt aus geht.
}
void calcPrims() {
int PrimzahlNummer = LastUnknown;
// System.out.println("LAstUnknown ist: " + LastUnknown);
Primzahlen[0] = 2;
Primzahlen[1] = 3;
long AktuelleZahl = Primzahlen[PrimzahlNummer - 1];
boolean IstPrimzahl;
// System.out.println("2");
// System.out.println("3");
int Limit = Primzahlen.length;
while(PrimzahlNummer < Limit) {
IstPrimzahl = true;
double WurzelDerAktuellenZahl = java.lang.Math.sqrt(AktuelleZahl);
for(int i = 1;i < PrimzahlNummer;i++) {
if(AktuelleZahl % Primzahlen[i] == 0) {
IstPrimzahl = false;
break;
}
if(Primzahlen[i] > WurzelDerAktuellenZahl) break;
}
if(IstPrimzahl) {
Primzahlen[PrimzahlNummer] = AktuelleZahl;
PrimzahlNummer++;
// System.out.println("" + AktuelleZahl);
}
AktuelleZahl = AktuelleZahl + 2;
}
for(long prim : Primzahlen) {
System.out.println("" + prim);
}
}
}
于 2012-04-23T19:46:21.880 に答える
0
私は約1年間、素数の検索に取り組んできました。これは私が最速であることがわかったものです：
import static java.lang.Math.sqrt;
import java.io.PrintWriter;
import java.io.File;
public class finder {
public static void main(String[] args) {
primelist primes = new primelist();
primes.insert(3);
primes.insert(5);
File file = new File("C:/Users/Richard/Desktop/directory/file0024.txt");
file.getParentFile().mkdirs();
long time = System.nanoTime();
try{
PrintWriter printWriter = new PrintWriter ("file0024.txt");
int linenum = 0;
printWriter.print("2");
printWriter.print (" , ");
printWriter.print("3");
printWriter.print (" , ");
int up;
int down;
for(int i =1; i<357913941;i++){//
if(linenum%10000==0){
printWriter.println ("");
linenum++;
}
down = i*6-1;
if(primes.check(down)){
primes.insert(down);
//System.out.println(i*6-1);
printWriter.print ( down );
printWriter.print (" , ");
linenum++;
}
up = i*6+1;
if(primes.check(up)){
primes.insert(up);
//System.out.println(i*6+1);
printWriter.print ( up );
printWriter.print (" , ");
linenum++;
}
}
printWriter.println ("Time to execute");
printWriter.println (System.nanoTime()-time);
//System.out.println(primes.length);
printWriter.close ();
}catch(Exception e){}
}
}
class node{
node next;
int x;
public node (){
node next;
x = 3;
}
public node(int z) {
node next;
x = z;
}
}
class primelist{
node first;
int length =0;
node current;
public void insert(int x){
node y = new node(x);
if(current == null){
current = y;
first = y;
}else{
current.next = y;
current = y;
}
length++;
}
public boolean check(int x){
int p = (int)sqrt(x);
node y = first;
for(int i = 0;i<length;i++){
if(y.x>p){
return true;
}else if(x%y.x ==0){
return false;
}
y = y.next;
}
return true;
}
}
1902465190909 ナノ秒で、2 から始まる 2147483629 に到達します。
于 2016-08-14T00:20:37.247 に答える
0
学習を始めたばかりなので、Pythonを使用してこれを作成しましたが、完全に正常に動作します。http://primes.utm.edu/lists/small/10000.txtに記載されているのと同じように、このコードによって 10,000 番目の素数が生成されます。nが素数かどうかを調べるには、 からまでnの数で割ります。この数の範囲のいずれかが完全に割り切れる場合、それは素数ではありません。2sqrt(n)n
import math
print ("You want prime till which number??")
a = input()
a = int(a)
x = 0
x = int(x)
count = 1
print("2 is prime number")
for c in range(3,a+1):
b = math.sqrt(c)
b = int(b)
x = 0
for b in range(2,b+1):
e = c % b
e = int(e)
if (e == 0):
x = x+1
if (x == 0):
print("%d is prime number" % c)
count = count + 1
print("Total number of prime till %d is %d" % (a,count))
于 2010-12-27T17:37:23.507 に答える
0
これは古い質問ですが、誰もが見逃しているものがあります...
素数の場合、この小さな試行分割はそれほど遅くはありません... 100 未満の素数は 25 個しかありません。テストする素数が非常に少なく、そのような小さな素数で、巧妙なトリックを引き出すことができます!
a が b と互いに素である場合、gcd ab = 1 です。互いに素です。楽しい言葉。素因数を共有していないことを意味します。したがって、1 回の GCD 呼び出しで複数の素数による割り切れる可能性をテストできます。幾つか？最初の 15 個の素数の積は 2^64 未満です。また、次の 10 の積も 2^64 未満です。必要なのは 25 個です。しかし、それは価値がありますか？
どれどれ：
check x = null $ filter ((==0) . (x `mod`)) $ [<primes up to 101>]
Prelude> length $ filter check [101,103..85600]
>>> 9975
(0.30 secs, 125,865,152 bytes
a = 16294579238595022365 :: Word64
b = 14290787196698157718
pre = [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]
primes = (pre ++) $ filter ((==1) . gcd a) $ filter ((==1) . gcd b) [99,101..85600]
main = print $ length primes
Prelude> main
>>> 10000
(0.05 secs, 36,387,520 bytes)
そこで6倍の改善。
(lengthは、リストを強制的に計算することです。デフォルトでは、Haskell は一度に 1 つの Unicode 文字を出力するため、実際にはリストを出力する時間が支配的であるか、使用される実際のコードの量を支配します。)
もちろん、これは GHCi (解釈されたコードを実行する repl) で古いラップトップ上で実行されており、これらの数値を s または s として解釈していませint64んBigInt。、しかしそれは醜く、実際には役に立ちません）。そこにあるすべての数値を、辞書検索を介して特定の型に特化できる一般化されたInteger のようなものとして解釈し、リンクされたリスト (コンパイルされていないため、ここでは融合されていません) を 3 回走査します。興味深いことに、2 つのフィルターを手動で融合すると、実際には REPL で速度が低下します。
コンパイルしましょう:
...\Haskell\8.6\Testbed>Primes.exe +RTS -s
10000
606,280 bytes allocated in the heap
Total time 0.000s ( 0.004s elapsed)
Windows のため、RTS レポートを使用します。一部の行は関連性がないために削除されました。それらは他の GC データであるか、実行の一部のみの測定値であり、合計すると 0.004 秒 (またはそれ以下) になります。また、Haskell は実際にはそれほど多くのことを行わないため、一定の折り畳みではありません。自分自身をコンスタント フォールドすると ( main = print 10000)、劇的に低い割り当てが得られます。
...Haskell\8.6\Testbed>Primes.exe +RTS -s
10000
47,688 bytes allocated in the heap
Total time 0.000s ( 0.001s elapsed)
文字通り、ランタイムをロードするのに十分なだけで、数値を出力して終了する以外に何もすることがないことを発見します。ホイール因数分解を追加しましょう:
wheel = scanl (+) 7 $ cycle [4, 2, 4, 2, 4, 6, 2, 6]
primes = (pre ++) $ filter ((==1) . gcd a) $ filter ((==1) . gcd b) $ takeWhile (<85600) wheel
Total time 0.000s ( 0.003s elapsed)
の参照に比べて約 1/3 削減されますがmain = print 10000、さらに最適化する余地があることは間違いありません。たとえば、そこでGCを実行するために実際に停止しましたが、微調整ではヒープの使用はありません。なんらかの理由で、ここでプロファイリング用にコンパイルすると、実際にはランタイムが 2 ミリ秒に短縮されます。
Tue Nov 12 21:13 2019 Time and Allocation Profiling Report (Final)
Primes.exe +RTS -p -RTS
total time = 0.00 secs (2 ticks @ 1000 us, 1 processor)
total alloc = 967,120 bytes (excludes profiling overheads)
今のところこれをそのままにしておきます。ランダムなジッターが支配的になり始めていると確信しています。
于 2019-11-13T02:49:48.077 に答える
-1
using System;
namespace ConsoleApplication2
{
class Program
{
static void Main(string[] args)
{
int n, i = 3, j, c;
Console.WriteLine("Please enter your integer: ");
n = Convert.ToInt32(Console.ReadLine());
if (n >= 1)
{
Console.WriteLine("First " + n + " Prime Numbers are");
Console.WriteLine("2");
}
for(j=2;j<=n;)
{
for(c=2;c<=i-1;c++)
{
if(i%c==0)
break;
}
if(c==i)
{
Console.WriteLine(i);
j++;
}
i++;
}
Console.Read();
}
}
}
于 2012-05-08T04:15:08.367 に答える