求素数

python解法

使用埃拉托斯特尼筛法

基本思想：素数的倍数一定不是素数
实现方法：用一个长度为N+1的数组保存信息（0表示素数，1表示非素数），先假设所有的数都是素数（初始化为0），从第一个素数2开始，把2的倍数都标记为非素数（置为1），一直到大于N；然后进行下一趟，找到2后面的下一个素数3，进行同样的处理，直到最后，数组中依然为0的数即为素数。
如果n*n > 范围最大值就跳出。

import math


def count_prime(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


start, end = map(int, input().split())
print(count_prime(end) - count_prime(start - 1))

要注意start要减去1。

def primeNum(m, n): # 正面思路时间复杂度不过关
    res = 0
    for i in range(m, n+1):
        for j in range(2, int(i**0.5)+1):
            if i%j == 0:
                break
        else:
            res += 1
    return res

def prime(n):    # 类似动态规划的思想
    res = [1]*(n+1)
    for i in range(2, int(n**0.5)+1):     # n**0.5可能不是int类型，注意
        for j in range(2, n):
            if i*j <= n:
                res[i*j] = 0         # 不是素数
            else:
                break
    return sum(res)

if __name__ == "__main__":
    m, n = map(int, input().split())
    print(prime(n) - prime(m-1))   # 注意包括边界

#include <iostream>
#include <stdio.h>
#include <cmath>
using namespace std;
int main(){
    int count=0;
    int M;
    int N;
    cin >> M;
    cin >> N;
    int flag=0;
    for(int i=M; i<=N; i++){
        flag=0;
        for(int j=2; j <= sqrt(i); j++){
            if(i%j==0){
                flag=1;
                break;
            }
        }
        if(flag==0){
                count++;
            }
    }
    cout << count;
    return 0;
}

#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 M,N;
    cin >> M >> N;
    int cnt = 0;   //记录区间内素数的个数
    for(int i = M; i <= N; i++)
    {
        if(isPrime(i))   
        {
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int m,n,sum=0;cin>>m>>n;
    for(int i=m;i<=n;i++)
    {
        int flag=0;
        for(int j=2;j*j<=i;j++)
            if(i%j==0)    {flag=1;break;}
        if(!flag) sum++;
    }
    cout<<sum;
}

using System;
using System.Collections.Generic;

//输入M、N，1 < M < N < 1000000，求区间[M,N]内的所有素数的个数。素数定义：除了1以外，只能被1和自己整除的自然数称为素数
namespace HalloWrold
{
    class ClassMain
    {
       static int lastLength = 0;
        static int b = 2;
   
        static void Main(string[] args)
        {
            //System.Console.ForegroundColor = System.ConsoleColor.Yellow;

            int n, m;
            string num = Console.ReadLine();
            n = Convert.ToInt32(num.Substring(0, num.IndexOf(" ")));
            m = Convert.ToInt32(num.Substring(num.LastIndexOf(" ")));
            int count = 0;
            

            List<int> arr = new List<int>();        //素数数组
            arr.Add(2);

            for (int i = 2; i <= m; i++)
            {
                int t = jd(arr.Count);
                for (int j = 0; j < t; j++)
                {
                    if (i % arr[j] == 0)
                        break;
                    if (j ==t- 1)
                    {
                        count++;
                        arr.Add(i);
                     
                    }
                }

            }
            if (m > 1)
                count++;
            Console.WriteLine(count);
        }

        public static int jd(int count)
        { 
            if (lastLength!= count.ToString().Length+1)             //说明位数变化
            {
                b *= 2;
                lastLength = count.ToString().Length + 1;      
            }
            
            if (count  <1000)
                return count;
            else
            {              
                return count / b;
            }
              
        }
    }

}

#include<stdio.h>
#include<math.h>
int main()
{
    int m=0,n=0;
    int j=0;
    int count=0;
    scanf("%d %d",&m,&n);
    for(int i=m;i<=n;i++)
    {
        for(j=2;j<=sqrt(i);j++)
        {
            if(i%j==0)
                break;
        }
        if(j>sqrt(i))
            count++;
    }
    printf("%d",count);
    return 0;
}

//埃氏筛法 复杂度 O(√nlogn)
 for (int i = 2; i*i <= num; ++i) {
        if (!mark[i]) {
            for (int j = i * i; j <= num; j += i) {
                mark[j] = 1;
            }
        }
    }

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int M=sc.nextInt();
        int N=sc.nextInt();
        boolean[] isPrime=new boolean[N+1];
        //注意2为素数
        isPrime[2]=true;
        for(int i=3;i<N+1;i++){
            if((i&1)==1){
                //先让奇数为true
                isPrime[i]=true;
            }
        }
        for(int i=3;i<=Math.sqrt(N);i+=2){
            if(isPrime[i]){
                for(int j=i+i;j<=N;j+=i){
                    isPrime[j]=false;
                }
            }
            
        }
        int count=0;
        for(int i=M;i<=N;i++){
            if(isPrime[i]){
                count++;
            }
        }
        System.out.println(count);
    }
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * 埃拉托斯特尼筛法 O(n*log(log(n)))
 * @author wylu
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strs = br.readLine().split(" ");

        int m = Integer.parseInt(strs[0]), n = Integer.parseInt(strs[1]);
        System.out.println(simpleSieve(m, n));
    }

    private static int simpleSieve(int m, int n) {
        //元素值为false表示该元素下标值为素数
        boolean[] mark = new boolean[n + 1];
        
        for (int i = 2; i <= n; i++) {
            if (!mark[i]) {
                for (int j = 2 * i; j <= n; j += i) {
                    mark[j] = true;
                }
            }
        }
        int count = 0;
        for (int i = m; i <= n; i++) {
            if (!mark[i]) count++;
        }
        return count;
    }
}