- 思路:我们可以建立一个大一点的数组,用来存储每个数是否是素数(素数用1表示,非素数用0表示),我们每找到一个素数就把他们的倍数变成非素数。
- 思路非常简单接下来就直接上代码吧
//这个是主要步骤的实现代码
for(int i = 2; i * i <= MAXSIZE; i++)
{
if(nums[i])
{
for(int j = i + i; j < MAXSIZE; j += i)
{
nums[j] = 0;
}
}
}
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100000005
int nums[MAXSIZE]={0, 0};
int main()
{
int n;
for(int i = 2; i < MAXSIZE; i++)
{
nums[i] = 1;
}
for(int i = 2; i * i <= MAXSIZE; i++)
{
if(nums[i])
{
for(int j = i + i; j < MAXSIZE; j += i)
{
nums[j] = 0;
}
}
}
printf("输入几组判断数据");
scanf("%d", &n);
while(n--)
{
int s;
scanf("%d", &s);
if(nums[s])
printf("是素数\n");
else
printf("不是素数\n");
}
return 0;
}