看流星社区 › C/C++技术分享 › [算法练习]找出40000以内的素数

tony_sun76421 发表于 2017-6-1 13:33:01

[算法练习]找出40000以内的素数

使用筛法
比如2是素数,那么2的倍数都不是素数,下一个是3 是素数,3的倍数都不是素数,下一个是5(4在前已经被排除了).....
#include <stdio.h>

#define MAXN 40000
int SPrime(void)
{
        int i = 0;
        int j = 0;
        int prinme = {0};
        int n = 0;

        for (i = 2; i < MAXN; i++)
        {
                prinme = 1;
        }

        for (i = 2; i < MAXN; i++)
        {
                if(prinme == 1)
                {
                        for (j = 2; i*j < MAXN; j++)//倍数置0
                        {
                                prinme = 0;
                        }
                }
        }

        freopen("output.txt", "w", stdout);
<span style="white-space:pre">        </span>//最后数组中为1的就是素数
        for (i = 0 ,j = 0; j < MAXN; j++)
        {
                if(prinme == 1)
        {
                        printf("%d ",j);
                        n++;
                        if(n == 13)
                        {
                                n = 0;
                                printf("\n");
                        }
                        i++;
                }
        }

        return i;
}

void main()
{
        int num = SPrime();
        printf("\n素数个数：%d\n",num);
        freopen( "CON", "w", stdout );

        printf("素数个数:%d\n具体数据见运行目录output.txt\n",num);
        getchar();
}

查看完整版本: [算法练习]找出40000以内的素数