目錄
?文章來源地址http://www.zghlxwxcb.cn/news/detail-448054.html
寫在前面：
輸出前20萬個素數(shù)，對比簡單遍歷和歐拉篩選的運(yùn)行時間。
簡單遍歷：
歐拉篩選：
一、簡單遍歷
二、遍歷至該數(shù)的平方根??? ??
三、用x/i來代替sqrt(x)
四、樸素篩法
五、埃式篩法
六、歐拉篩法????????
?文章來源：http://www.zghlxwxcb.cn/news/detail-448054.html
寫在前面：
輸出前20萬個素數(shù)，對比簡單遍歷和歐拉篩選的運(yùn)行時間。
簡單遍歷：
#include <stdio.h>
#include <time.h>
clock_t start, stop;
double duration;
int main()
{
int count = 0;
start = clock(); /*開始計時*/
int i, j;
for (i = 2; i <= 200000; i++) {
int isprime = 1;
for (j = 2; j < i; j++) {
if (i % j == 0) {
isprime = 0;
break;
}
}
if (isprime == 1) {
printf("%d\n", i);
count++;
}
}
printf("%d\n", count);
stop = clock(); /*停止計時*/
duration = ((double)(stop - start)) / CLK_TCK; /*計算運(yùn)行時間*/
printf("Running time: %lf seconds\n", duration); // 輸出運(yùn)行時間
return 0;
}
3.243秒
歐拉篩選：
#include <stdio.h>
#include <stdbool.h>
#include <time.h>
clock_t start, stop;
double duration;
int main()
{
int n = 200000;
bool isPrime[200001];
int prime[200001];
int cnt = 0; //記錄素數(shù)的個數(shù)
for (int i = 2; i <= n; i++)
isPrime[i] = true;
for (int i = 2; i <= n; i++)
{
if (isPrime[i])
{
prime[cnt] = i; //將i加入素數(shù)數(shù)組
cnt++;
}
for (int j = 0; j < cnt && i * prime[j] <= n; j++)
{
isPrime[i * prime[j]] = false; //將當(dāng)前數(shù)與質(zhì)因數(shù)的積標(biāo)記為合數(shù)
if (i % prime[j] == 0)
break; //保證每個合數(shù)只會被它的最小質(zhì)因數(shù)篩選一次
}
}
printf("素數(shù)：\n");
for (int i = 0; i < cnt; i++)
{
printf("%d\n", prime[i]);
}
printf("共有素數(shù)%d個\n", cnt);
stop = clock(); /*停止計時*/
duration = ((double)(stop - start)) / CLOCKS_PER_SEC; /*計算運(yùn)行時間*/
printf("Running time: %lf seconds\n", duration); // 輸出運(yùn)行時間
return 0;
}
0.353秒
?
一、簡單遍歷
????????這是一個簡單的C語言程序，實(shí)現(xiàn)的功能是打印出2到100之間的所有素數(shù)。
????????程序的基本思路是：用變量i從2開始逐個遍歷到100，對于每一個i，用變量j從2開始逐個遍歷到i-1，如果i能被j整除，則說明i不是素數(shù)，將isPrime標(biāo)志位設(shè)為0，然后跳出循環(huán)。如果在循環(huán)結(jié)束后isPrime仍然是1，則說明i是素數(shù)，將其打印出來即可。
#include <stdio.h>
int main() {
int i, j;
for (i = 2; i <= 100; i++) {
int isPrime = 1;
for (j = 2; j < i; j++) {
if (i % j == 0) {
isPrime = 0;
break;
}
}
if (isPrime == 1) {
printf("%d\n", i);
}
}
return 0;
}二、遍歷至該數(shù)的平方根??? ??
????????程序的基本思路是：定義一個isprime函數(shù)，用來判斷一個數(shù)是否為素數(shù)。isprime函數(shù)的實(shí)現(xiàn)方式與之前的程序相同，用一個循環(huán)遍歷到該數(shù)的平方根即可。
????????在主函數(shù)中，用for循環(huán)逐個枚舉2到n之間的數(shù)字，如果這個數(shù)字是素數(shù)就打印出來，并將cnt計數(shù)器自增。最后輸出素數(shù)的總個數(shù)。
????????相較于之前的程序，這個程序代碼更加簡潔，可讀性也更好，而且使用了一個新的函數(shù)來判斷素數(shù)，使得程序更加模塊化，代碼復(fù)用性更高。
#include<stdio.h>
#include<math.h>
bool isprime(int x)
{
for (int i = 2; i <=sqrt(x); i++)
{
if (x % i == 0) return 0;
}
return 1;
}
int main()
{
int n, cnt = 0;
scanf("%d", &n);
for (int i = 2; i <= n; i++)
{
if (isprime(i))
{
cnt++;
printf("%d\n", i);
}
}
return 0;
}三、用x/i來代替sqrt(x)
????????對于i<=sqrt(x) sqrt函數(shù)的計算會比較慢，因此我們兩邊平方后，移一個i過去右邊，變成i<=x/i 這樣就能避免溢出的問題 。程序的代碼基本與之前的程序相同，只是在函數(shù)isprime中的循環(huán)控制條件做了一下優(yōu)化，用x/i來代替sqrt(x)，達(dá)到減少循環(huán)次數(shù)的效果。
#include<stdio.h>
bool isprime(int x)
{
for (int i = 2; i <= x / i; i++)
{
if (x % i == 0) return 0;
}
return 1;
}
int main()
{
int n,cnt=0;
double t1 = clock();
scanf("%d", &n);
for (int i = 2; i <= n; i++)
{
if (isprime(i))
{
cnt++;
printf("%d\n", i);
}
}
return 0;
}四、樸素篩法
????????一個合數(shù)一定存在非1非本身的質(zhì)因子。
????????程序的基本思路是：首先定義一個長度為n的數(shù)組pri，用來記錄每一個數(shù)字是否是素數(shù)。然后用for循環(huán)遍歷到n的平方根，如果i是素數(shù)，則用一個內(nèi)部循環(huán)依次去除i的倍數(shù)，將這些數(shù)標(biāo)記為合數(shù)。最后再用for循環(huán)遍歷整個數(shù)組，將所有沒有被標(biāo)記過的數(shù)字輸出出來。
????????這個算法的優(yōu)點(diǎn)在于避免了之前程序內(nèi)部判斷素數(shù)時的重復(fù)計算，同時減少了程序的循環(huán)次數(shù)。缺點(diǎn)是需要用一個數(shù)組來存儲中間狀態(tài)，可能會消耗更多的內(nèi)存。
#include<stdio.h>
//0為素數(shù)，1為合數(shù)
int pri[100] = {0};
int main()
{
int n,cnt=0;
double t1 = clock();
scanf("%d", &n);
for (int i = 2; i <= n/i; i++)
{
if (!pri[i])//沒被篩過
{
for (int j = 2 * i; j <= n; j += i)//去除合數(shù)
{
pri[j] = 1;
}
}
}
for (int i = 2; i <= n; i++)
{
if (!pri[i])
{
cnt++;
printf("%d\n", i);
}
}
return 0;
}五、埃式篩法
? ? ? ? 該程序是樸素篩法程序的一個修正，主要在內(nèi)部循環(huán)的控制條件上做了改變。
????????由于在之前的程序中，內(nèi)部循環(huán)是從2 * i開始依次將i的倍數(shù)標(biāo)記為合數(shù)。但在這個程序中，內(nèi)部循環(huán)是從i * i開始依次將i的倍數(shù)標(biāo)記為合數(shù)。這是因?yàn)樵趇 * i之前，這些數(shù)字已經(jīng)被其他的素數(shù)篩選過了，所以不需要再次去除。
????????這個算法的優(yōu)點(diǎn)和上一個程序的優(yōu)點(diǎn)一樣，避免了之前程序的重復(fù)計算，減少了程序的循環(huán)次數(shù)。同時由于內(nèi)部循環(huán)的起始位置不同，也稍微提高了一點(diǎn)點(diǎn)程序的執(zhí)行效率。
#include<stdio.h>
int pri[100] = {0};
int main()
{
int n,cnt=0;
double t1 = clock();
scanf("%d", &n);
for (int i = 2; i <= n/i; i++)
{
if (!pri[i])//沒被篩過
{
for (int j = i * i; j <= n; j += i)//去除合數(shù)
{
pri[j] = 1;
}
}
}
for (int i = 2; i <= n; i++)
{
if (!pri[i])
{
cnt++;
printf("%d\n", i);
}
}
return 0;
}六、歐拉篩法????????
????????歐拉篩法是一種高效的求解素數(shù)的算法，其本質(zhì)基于線性篩法的思想。
????????歐拉篩法的核心思想是篩去每個數(shù)的所有質(zhì)因數(shù)，使得每個數(shù)只被它的最小質(zhì)因數(shù)篩選一次。首先將2到n范圍內(nèi)的所有數(shù)都標(biāo)記為素數(shù)，然后從2開始循環(huán)到n，對于每個數(shù)i，如果它是素數(shù)，則將其加入素數(shù)數(shù)組中，并將它的所有倍數(shù)（除了它本身）標(biāo)記為合數(shù)。對于一個合數(shù)i*j，它已經(jīng)被i篩選過了，所以其最小質(zhì)因數(shù)一定是i，因此只需要將其標(biāo)記一次即可。
????????另外，為了保證每個合數(shù)都只會被它的最小質(zhì)因數(shù)篩選一次，算法中添加了一個優(yōu)化條件，即當(dāng)i能夠整除當(dāng)前質(zhì)數(shù)數(shù)組中的某個數(shù)j時，直接將i*j標(biāo)記為合數(shù)，跳過后續(xù)的循環(huán)過程。
????????歐拉篩法的時間復(fù)雜度為O(n)，相比于樸素篩法和埃式篩法，具有更高的效率和更低的時間復(fù)雜度。
#include <stdio.h>
#include <stdbool.h>
int main()
{
int n = 100;
bool isPrime[101];
int prime[101];
int cnt = 0; //記錄素數(shù)的個數(shù)
for (int i = 2; i <= n; i++)
isPrime[i] = true;
for (int i = 2; i <= n; i++)
{
if (isPrime[i])
{
prime[cnt++] = i; //將i加入素數(shù)數(shù)組
}
for (int j = 0; j < cnt && i * prime[j] <= n; j++)
{
isPrime[i * prime[j]] = false; //將當(dāng)前數(shù)與質(zhì)因數(shù)的積標(biāo)記為合數(shù)
if (i % prime[j] == 0)
break; //優(yōu)化，保證每個合數(shù)只會被它的最小質(zhì)因數(shù)篩選一次
}
}
for (int i = 0; i < cnt; i++)
{
printf("%d\n", prime[i]);
}
return 0;
}?
?
?
到了這里，關(guān)于C語言 五種方法輸出100以內(nèi)的素數(shù)（質(zhì)數(shù)） 源碼的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
