请考虑性能
使用 普通筛选法--埃拉托斯特尼筛法
先简单说一下原理:
基本思想:素数的倍数一定不是素数
实现方法:用一个长度为N+1的数组保存信息(0表示素数,1表示非素数),先假设所有的数都是素数(初始化为0),从第一个素数2开始,把2的倍数都标记为非素数(置为1),一直到大于N;然后进行下一趟,找到2后面的下一个素数3,进行同样的处理,直到最后,数组中依然为0的数即为素数。
如果n*n > 范围最大值就跳出。
import math
def countPrime(N):
n = int(math.sqrt(N) + 1)
arr = [True] * (N+1)
for i in range(2, n):
for j in range(2, N):
if i * j <= N:
arr[i * j] = False
else:
break
return sum(arr) - 2
print(countPrime(int(input())))
import java.math.BigInteger; import java.util.*; public class Main { private static final int N_MAX = 105; private static StringBuilder sb = new StringBuilder(); private static ArrayList<Integer> primers = new ArrayList<>(); public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int count = 0; for (int i=2; i<n; i++) { if (judge(i)) count++; } System.out.println(count); } private static boolean judge(int n) { if (n == 0) { return false;}; for (Integer p: primers) { if ( n % p == 0) return false; } primers.add(n); return true; } }
#include <bits/stdc++.h> using namespace std; bool isPrime(int n) //判断一个数是否为素数 { if(n<=1) { return false; } else { for (int i = 2; i <= sqrt(n); i++) { if(n%i == 0) { return false; } } return true; } } int main() { int n; cin >> n; int cnt = 0; for (int i = 1; i < n; ++i) { if(isPrime(i)) { cnt++; } } cout << cnt << endl; return 0; }
package main import ( "fmt" ) func main() { var n int fmt.Scan(&n) ans:=0 for i:=2;i<n;i++{ if check(i){ ans++ } } fmt.Print(ans) } func check(x int)bool{ if x==2{ return true } if x>2&&x%2==0{ return false } for i:=3;i<x;i+=2{ if x%i==0{ return false } } return true }
#include<iostream> using namespace std; bool a[100001]; int s=0; int main() { int n; cin>>n; for (int i=4;i<=n;i+=2) a[i]=1; for (int i=2;i<=n;i++) { if (a[i]==1) continue; s++; if (i*i>n) continue; for (int j=i*i;j<=n;j+=i) a[j]=1; } cout<<s; return 0; }这题用普通的筛选法,加上一个简单的优化就行
#include<bits/stdc++.h> using namespace std; int N; int x[1000001]; //用筛法求指质数 long long ans = 0; int main(){ memset(x,0,sizeof(x)); scanf("%d",&N); for(int i = 1;i < N;i++){ if(i==1) continue; //1不是质数,不用管 if(x[i]==0){ //若没有被筛掉,说明是质数 ans++; for(int j = i+i;j <= N;j += i){ //筛去所有质数的倍数,注意减少枚举的范围 x[j] = 1; } } } printf("%d",ans); return 0; }
#include <iostream> using namespace std; const int N = 1e6 + 7; int primes[N], cnt; bool st[N]; void getPrimes(int n) { for (int i = 2; i <= n; i ++) { if (!st[i]) { primes[cnt ++] = i; for (int j = i + i; j <= n; j += i) st[j] = true; } } } int main() { int n; cin >> n; getPrimes(n); cout << cnt << endl; return 0; }
#include <vector> #include <iostream> using namespace std; int main() { int N; cin >> N; if (N == 2) return 0; int res(1); vector<bool> ns(true, N + 1); for (int i = 3; i <= N; i += 2) { if (ns[i]) res++; for (int j = i * i, add = 2 * i; j <= N; j += add) { ns[j] = false; } } cout << res << endl; return 0; }
可以说是筛法最简洁的版本了
while True: try: n=int(input().strip()) num=0 def iszhishu(i): num=i//2 result=True if num==0: result= False else: for j in range(1,num+1): if j!=1 and i%j==0: result= False return result if n<=1: print(0) else: for i in range(2,n): #print(i) if iszhishu(i): #print(i) num+=1 print(num) except: break
import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc=new Scanner(System.in); int n=Integer.valueOf(sc.next()); if(n<=1) System.out.println(0); else if(n==2) System.out.println(1); else{ int ans=1; for(int i=3;i<=n;i+=2){ if(isSu(i)) ans++; } System.out.println(ans); } } public static boolean isSu(int num){ for(int i=2;i<=Math.sqrt(num);i++){ if(num%i==0) return false; } return true; } }
效率可能有点低
如果知道n的范围,可以先进行预处理,会快很多
import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int sum = isPrime(n); System.out.println(sum); in.close(); } private static int isPrime(int n) { int[] a = new int[n]; Arrays.fill(a, 2, n, 1); for (int i = 2; i < n; i++) { if (a[i] == 1) { for (int j = i << 1; j < n; j += i) { a[j] = 0; } } } int cnt = 0; for (int i = 0; i < n; i++) { if (a[i] == 1) { cnt++; } } return cnt; } }
#include<stdio.h> #include<stdlib.h> #include<string.h> int main() { unsigned char *p = NULL; int i, j, n; int num = 0; scanf("%d",&n); p = (unsigned char *)malloc(n*sizeof(unsigned char)); memset(p, 1, n); p[0] = p[1] = 0; for(i=4; i<n; i+=2) { p[i] = 0; } for(i=3; i*i<n; i+=2) { if(p[i]) { for(j=i+i; j<n; j+=i) { p[j] = 0; } } } for(i=2; i<n; i++) { if(p[i]) { num++; } } printf("%d\n",num); free(p); return 0; }