C语言：用筛选法求100以内的素数。

Question

如题所述

Answer 1

#include<iostream>
using namespace std;
int main()
{
int prime(int);
int n;
cout<<"input an integer:";
cin>>n;
if(prime(n))
{
cout<<n<<"is a prime."<<endl;
}
else
{
cout<<n<<"is not a prime."<<endl;
}
return 0;
}

int prime(int n)
{
int flag=1,i;
for(i=2;i<n/2&&flag==1;i++)
{
if(n%i==0)
{
flag=0;
}
return(flag);
}
}

//筛选法
#include<iostream.h>
#include<iomanip.h>
#include<cmath>
void main()
{
int i,j,n,a[101]; //定义a数组包含101个元素
for(i=1;i<=100;i++) //a【0】不用，只用a【1】~a【100】
{
a[i]=i; //使a【1】~a【100】的值为1~100
}
a[1]=0; //先挖掉a【1】
for(i=2;i<sqrt(100);i++)
{
for(j=i+1;j<=100;j++)
{
if(a[i]!=0&&a[j]!=0)
if(a[j]%a[i]==0)
a[j]=0; //把非素数挖掉
}
cout<<endl;
}
for(i=1,n=0;i<=100;i++)
{
if(a[i]!=0) //选出值不为0的数组元素，即素数
{
cout<<setw(5)<<a[i]<<" "; //输出素数，域宽为5
n++; //计数器，累计本行已输出的数据个数
}
if(n==10) //输出10个数后换行
{
cout<<endl;
n=0;
}
}
cout<<endl;
}

Answer 2

int notPrime[101];

int main()
{
int i,j;
for(i=2;i<=100;i++)
if(!notPrime[i]) {
printf("%d is a prime number\n",i);
for(j=i*i;j<=100;j+=i) notPrime[j] = 1;
}
}本回答被提问者和网友采纳