判決素數個數

總時間限制:

1000ms

記憶體限制:

65536kB

描述

輸入兩個整數X和Y，輸出兩者之間的素數個數（包括X和Y）。

輸入

兩個整數X和Y（1 <= X,Y <= 105）。

輸出

輸出一個整數，表示X，Y之間的素數個數（包括X和Y）。

樣例輸入

1 100      

樣例輸出

25      

————————————————————————————————————————————————————

思路：兩個坑：1.未說明x,y誰大。2.時間逾時，需要剪枝。

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<string>
#include<iostream>
#include<cstring>
#include<sstream>
using namespace std;
int check(int i){
	int flag=0;
	for(int j=2;j*j<=i;j++){
		if(i%j==0){
			flag++;break;
		}
	}
	if(flag!=0) return 0;
	else return 1;
}
int main(){
	int start,end;int ans=0;
	(cin>>start>>end).get();
	if(start<=end){
	for(int i=start;i<=end;i++){
		if(i==1){continue;}
		if(i==2){
			ans++;continue;
		}
		if(i!=2&&i!=1&&check(i)){
			ans++;
		}
	}
}
if(start>end){
	int temp;
	temp = start;
	start = end;
	end = temp;
	for(int i=start;i<=end;i++){
		if(i==1){continue;}
		if(i==2){
			ans++;continue;
		}
		if(i!=2&&i!=1&&check(i)){
			ans++;
		}
	}
}
	cout<<ans<<endl;
}