密码工程-小素数

密码工程-小素数
20201331黄文刚
任务详情

0. 在openEuler(推荐)或Ubuntu或Windows(不推荐)中完成下面任务
1. 参考《密码工程》p107伪代码基于Eratosthenes算法实现 int SmallPrimeList(int n, int *plist, int *len), 其中plist返回素数列表，len
   返回列表长度
   2 写出测试代码，至少包括 n=2, n=你的四位学号，n>2^20次方的测试代码,提交代码和运行结果截图

代码

#include <stdio.h>
#include <stdlib.h>
#define n 1050000

int main(void) {
    int i, j;
    int count=0;
    int prime[n+1];

    for(i = 2; i <= n; i++)
        prime[i] = 1;

    for(i = 2; i*i <= n; i++) 
    { 
        if(prime[i] == 1) 
        {
            for(j = 2*i; j <= n; j++) 
            {
                if(j % i == 0)
                    prime[j] = 0;
            }
        }
    }
    //printf prime and count
    for(i = 2; i < n; i++) 
    {
        if(prime[i] == 1) 
        {
            printf("%4d ", i);
            count++;
            if(i % 16 == 0)
                printf("\n");
        }
    }
    printf("\nThe number of prime is:%d\n",count);
    return 0;
}

运行截图
n=2

n=1331

n>2^20 （测试的是n=1050000）