请考虑性能
// 简单筛法求素数
#include<iostream>
#include<cstring>
#define MAXN 100001
using namespace std;
bool prim[MAXN] = {true};
int main(int argc, char** argv){
memset(prim, 1, sizeof(prim));
prim[0] = false;
prim[1] = false;
for(int i = 2; i < MAXN; ++i){
if(prim[i]){
for(int j = i*i; j < MAXN; j+=i){
prim[j] = false;
}
}
}
int num, count = 0;
cin>>num;
for(int i = 2; i <= num; i++){
if (prim[i]){
count++;
}
}
cout<<count<<endl;
}
importjava.util.*; publicclassMain{ publicstaticvoidmain(String[] args){ Scanner sc = newScanner(System.in); intn = sc.nextInt(); //int m = (int)(Math.sqrt(n)); intcount = 0; if(n<=1) { count=0; } elseif(n==2) { count=1; } elseif(n==3) { count=2; } else { for(inti=2;i<n;i++) { booleanflag = true; for(intj=2;j<=(int)(Math.sqrt(i));j++) { if(i%j==0) { flag = false; break; } // break; } if(flag) { count++; } } } System.out.println(count); } } |
#include <iostream> #include <math.h> bool isPrime(int num) { if(num < 2) { return false; } else if (num == 2) { return true; } else { int k = (int)sqrt(num); if (num % 2 == 0) { return false; } for(int i = 3; i <= k; i+=2) { if (num % i == 0) { return false; } } return true; } } int main() { int num; scanf("%d",&num); int count = 0; for(int i = 0; i < num; i++) { if(isPrime(i)){ count++; } } printf("%d",count); return 0; }