返回小于 N 的质数个数

python解法

使用 普通筛选法--埃拉托斯特尼筛法
先简单说一下原理：
基本思想：素数的倍数一定不是素数
实现方法：用一个长度为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<stdio.h>
#include<math.h>
int main()
{
    int N=0,count=0,i,j;
    scanf("%d",&N);
    for(i=2;i<=N;i++)
    {
        int k=i;
        for(j=2;j<=sqrt(k);j++)
        {
            if(k%j==0)
                break;
        }
        if(j>sqrt(k))
        {
            count++;
        }
    }
    printf("%d\n",count);
    return 0;
}

#include <iostream>
using namespace std;
int main()
{
	int n;
	cin >> n;
	//计数
	int count = 0;
	for (int i = 2; i <= n; i++)
	{
		for (int j = 2; j <= i; j++)
		{
			if (j<i && i % j == 0)
			{
				break;
			}
			if (i == j)
			{
				count++;
			}
		}
	}
	cout << count << endl;
	return 0;
}

#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;
}

n = int(input())

if n < 3:
    c = 0
    print(c)
else:
    c = 0
    for i in range(3,n):
        for j in range(2,i):
            if i % j == 0:
                c += 1  #只要不是素数就加1
                break
    print(n -2 -c) #总数-2-合数就是素数的个数

#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;
}