欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

求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循环解答

相关标签: c++