求N以内的素数
程序员文章站
2024-03-15 15:20:36
...
求N以内的素数
题目:
求1,2,…,N中素数的个数
输入格式:
一个整数N
输出格式:
一个整数,表示素数的个数
输入样例:
10
输出样例:
4
#include<iostream>
using namespace std;
int main(){
int n,num=0;
cin>>n;
if(n==1){
cout<<"0";
return 0;
} //1不是素数特判
for(int i=2;i<=n;i++){
int k=0;//1、统计因子个数变量赋初值为0
for(int j=2;j*j<=i;j++)
if(i%j==0){
k++;
break;
}//2、统计因子个数(只要找到一个即可证明不是素数,立即中断,节约时间)
if(k==0) num++; //3、统计素数的个数(无因子的才是素数)
}
cout<<num;
return 0;
}
素数的定义:只能被1和自己本身整除的数
所以如果输入1,直接输出0
如果输入的数大于1,使用双重for循环解答
上一篇: 筛选法求素数
下一篇: 筛选法求n以内的素数