If you give someone a program , you will frustrate them for a day; if you teach them how to program, you will frustrate them for a lifetime.IT 這段話的意思是，如果你交給某人一隻程式，你將折磨他一整天;如果你教會某人如何寫程式，你將折磨他一輩子。

部落格全站分類：數位生活

BloggerAds

Dec 14 Thu 2017 00:58
素數高效率篩選法 - acm1314

文章出處

無需多言直接上代碼吧！

 1 //Eratosthenes 篩法（埃拉托斯特尼篩法）
 2 memset(check, false, sizeof(check))
 3 int tot = 0;
 4 for(int i=2; i<=N; i++)
 5     if(!check[i]) 
 6     {
 7         prime[tot++] = i;
 8         for(int j=i*2; j<=N; j+=i)
 9         check[j] = true;
10     }
11 
12 //Euler 篩法（歐拉篩法）--線性篩選
13 memset(check, false, sizeof(check));
14 int tot = 0;
15 for(int i=2; i<=N; i++)
16 {
17     if(!check[i]) prime[tot++] = i;
18     for(int j=0; j<tot; j++)
19     {
20         if(i*prime[j]>N) break;
21         check[i*prime[j]] = true;
22         if(i % prime[j]==0) break;
23     } 
24 }