求素数

//通过时间:8ms  占用内存:1400kb
#include<iostream>
#define K 1000001
using namespace std;
char p[K+1] = {1,1,0};
int main() {
    int i,j;
    for(i = 2; i <= K/10; ++i)
        if(!p[i])
            for(j = 2; i*j <=K ; ++j)
                p[i*j] = 1;
    int M,N,count;
    cin>>M;
    cin>>N;
    count=0;
    for(i=M; i<=N; i++)
        if(!p[i])
            count++;
    cout<<count;
}

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> isp;
int a[1000001],l,r,m,n;
void init(){
    a[0]=a[1]=1;
    for(int i=2;i<=1000000;i++)
        if(!a[i]){
            for(int j=2*i;j<=1000000;j+=i) a[j]=1;
            isp.push_back(i);
        }
}
int main(){
    init();
    while(scanf("%d%d",&m,&n)!=EOF){
        l=lower_bound(isp.begin(),isp.end(),m)-isp.begin();
        r=upper_bound(isp.begin(),isp.end(),n)-isp.begin();
        printf("%d\n",r-l);
    }
}

import java.util.ArrayList;
import java.util.Scanner;
public class Main {
    private static int calPrimeNumber(int begin,int end){
        boolean[] prime=new boolean[end+1];
        for(int i=begin;i<prime.length;i++){
            if(i%2 == 0){
                prime[i]=false;
            }else{
                prime[i]=true;
            }
        }
        for(int i=3;i<=Math.sqrt(1.00*end);i+=2){
            for(int j=i+i;j<=end;j+=i){
                prime[j]=false;
            }
        }
        prime[2]=true;

        int count=0;
        for(int i=begin;i<=end;i++){
            if(prime[i]){
                count++;
            }
        }
        return  count;
    }
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int m=in.nextInt();
        int n=in.nextInt();
        int sum=calPrimeNumber(m,n);
        System.out.println(sum);
    }
}

//语言：C++  运行时间：14 ms 占用内存：4976K
//筛法求N以内的素数
//原理：www.cnblogs.com/xiaoxi666/p/7172440.html #include <iostream>
#include <cmath>
#include <vector>
using namespace std;
///寻找N以内的质数的个数
size_t find_Prime(int N)
{
    if(1==N)
        return 0;
 
    vector<int> prime_tmp(N,1);
    for(int i=0; 2*i+3<=sqrt(N); i++)
    {
        if(prime_tmp[i])
            for(int j=(2*i+3)+i; j<N; j+=(2*i+3))
                prime_tmp[j]=0;
    }
    vector<int> prime;//新开了一个，用来保存素数
    prime.push_back(2);
    for(int i=0; i<N; i++)
    {
        if(prime_tmp[i] && 2*i+3<=N)//说明是质数，按照质数的方法处理
        {
            prime.push_back(2*i+3);
        }
    }
 
    return prime.size();//prime保存了小于等于N的素数
}
 
int main()
{
    int M,N;
    while(cin>>M>>N){
        cout<<find_Prime(N)-find_Prime(M-1)<<endl;
    }
    return 0;
}

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdbool.h>

#define sc scanf
#define pr printf
#define N 999999
bool sushu[N];
 void test() {
		for (int i = 0; i <N; i++) {
			sushu[i] = 1;    //假设全部为素数
		}
		sushu[0] = sushu[1] = 0;
		for (int i = 2; i < N; i++) {
			if (sushu[i]) {
				for (int j = i + i; j <N; j += i) {
					sushu[j] = 0;
				}
			}
		}
}
int a, b;
int main() {
	test();
	int flag = 0;
	sc("%d %d", &a, &b);
	
   for (int i = a; i <b; i++) {
	   if (sushu[i]) {
		   flag++;
	   }
}
		pr("%d", flag);
		return 0;
}

print(len([str(item) for item in filter(lambda x: not [x % i for i in range(2, x) if x % i == 0], range(a, b))]))

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <cstring>
#include <math.h>

using namespace std;

int is_sure(int n)
{
	int tmp = (int)sqrt(n);
	for (int i = 2; i <= tmp; i++)
		if (n%i == 0)	return 0;
	return 1;
}

int main(int argc, char **argv)
{
	int l, r;
	while (cin >> l >> r)
	{
		int cnt = 0;
		for (int i = l; i <= r; i++)
			is_sure(i) && ++cnt;
		cout << "" << cnt << endl;
	}

	return 0;
}

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        scanner.close();

        int sum = 0;
        int temp = 2;
        boolean flag = false;
        for (int i = m; i <= n; ++i)
        {
            if (i == 2){
                sum += 1;
                continue;
            }
            if (i % 2 == 0)
                continue;
            while (temp <= Math.sqrt(i)){
                if (i % temp == 0)
                {
                    flag = true;
                    break;
                }
                ++temp;
            }

            if (flag){
                flag = false;
                temp = 2;
                continue;
            }
            temp = 2;
            sum += 1;
        }
        System.out.println(sum);
    }
}

h = 0
leap = 1
from math import sqrt
from sys import stdout
lower = int(input("输入区间最小值: "))
upper = int(input("输入区间最大值: "))
for m in range(lower,upper+1):
    k = int(sqrt(m + 1))
    for i in range(2,k + 1):
        if m % i == 0:
            leap = 0
            break
    if leap == 1:
       # print '%-4d' % m
        h += 1
        #if h % 10 == 0:
         #   print ''
    leap = 1
print '%d' % h 

#include <iostream>
#include <stdlib.h>
#include <math.h>
using namespace std;

int FindPrime(int n)
{
	if (n < 3)
		return 0;

	bool *prime = new bool[n];
	for (int i = 0; i < n; ++i)
		i % 2 == 0 ? prime[i] = false : prime[i] = true;
	for (int i = 3; i < sqrt(n); ++i)
	{
		if (prime[i] == true)
		{
			for (int k = 2 * i; k < n; k += i)
				prime[k] = false;
		}
	}

	int cnt = 0;
	for (int i = 0; i < n; ++i)
	{
		if (prime[i] == true)
			++cnt;
	}
	return cnt;
}

int main()
{
	int m, n;
	while (cin >> m >> n)
	{
		cout << FindPrime(n) - FindPrime(m) << endl;
	}
}

public class prime {
	public static void main(String[] args) {
		//判断区间内有几个素数
		countPrime()；
	}
	private static void countPrime(){
		Scanner sc = new Scanner(System.in);
		int start = sc.nextInt();
		int end = sc.nextInt();	
		int count = 0;
		for (int i = start; i <= end; i++) {
			if (i != 1) {
				int flag = 0;
				for (int j = 2; j < i; j++) {
					if (i % j == 0) {
						flag = 1;
						break;
					}
				}
			if (flag == 0){
				count++;
			}	
		}
	}	
	System.out.println(count);
  }
}

	#include <iostream>



	#include <vector>



	#include <math.h>



	using namespace std;



	intmain()



	{



	    constlonglonglength = 1000001;



	    vector<int> data(length, 1);



	    for(inti = 2; i < sqrt(length); i++)



	    {



	        if(data[i] == 1)



	        {



	            for(intj = i+i; j < length; j+=i)



	                data[j] = 0;       



	        }



	    }



	    intm, n;



	    while(cin >> m >> n)



	    {



	        intsum = 0;



	        for(inti = m; i <= n; i++)



	            if(data[i] == 1)



	                sum++;



	        cout << sum << endl;



	    }



	    return0;



	}

	#include<iostream>



	#include<math.h>



	using namespace std;



	 



	intmain()



	{



	    intm,n;



	    cin>>m;



	    cin>>n;



	    intk=0;



	    for(inti=m;i<=n;i++)



	    {   for(intj=2;j<=sqrt(i);j++)



	            {if(i%j==0)



	                {k++;



	                break;



	                }



	            }



	    }



	    cout<<n-m+1-k<<endl;   



	    return0;



	 



	}