【题目描述】
编程求2~n(n为大于2的正整数)中有多少个素数。
【输入描述】
输入n (2<= n <=50000)
【输出描述】

素数个数
【输入样例】
10
【输出样例】

4

#include<iostream>
#include<cmath>
using namespace std;
bool judge(int x);
int main()
{
    int n;
    int i;
    int sum=0;
 
    cin>>n;
    for(i=2; i<=n; i++)
        if(judge(i))//若是素数
            sum++;//累加素数个数
    cout<<sum<<endl;
 
    return 0;
}
bool judge(int x)//判断素数
{
    int i=2;
    while(i<=floor(sqrt(x))&&(x%i)!=0)
        i++;
    if(i>floor(sqrt(x)))
        return true;
    return false;
}

// 判断素数的几种方式
// 1 定义法(除了1和他本身之外,没有任何一个数能被整除)(试除法)
bool is_prime3(unsigned long long n) { //slow
	for (int i = 2; i < n - 1; i++) {
		if (n % i == 0) {
			return 0;
		}
	}
	return 1;
}
// 2. 改进
/*
根据如果一个数是合数,那么它的最小质因数肯定小于等于它的平方根。
用反证法可以证明一下。假设x是n的最小质因数,则存在n/x=p。p>x,x*p=n。如果x不小于等于它的平方根,则x*x>n,而p>x,故x*p>n,假设不成立。合数是与质数相对应的自然数。一个大于1的自然数如果它不是合数,则它是质数。也就是说如果一个数能被它的最小质因数整除的话,那它肯定是合数,即不是质数。所以判断一个数是否是质数,只需判断它是否能被小于它开跟号后的所有数整除,因此,这样做的运算少了很多,降低了时间复杂度。
*/
int isprime(int m)
{
    int i;
    for(i=2;i<=sqrt(m);i++)    /*sqrt(int n)这个函数需要引入math.h头文件*/
      if(m%i==0)
        return 0;
      else
        return 1;
}
// 3 查表法

// 4.孪生素数
/*
孪生素数: 所谓孪生素数指的是间隔为 2 的相邻素数,它们之间的距离已经近得不能再近了。

若n≥6且n-1和n+1为孪生素数,那么n一定是6的倍数。
证明:
∵ n-1和n+1是素数 ┈┈┈┈┈ ①
∴ n-1和n+1是奇数
∴ n是偶数,即n是2的倍数 ┈┈┈┈┈ ②
假设n不是3的倍数,得:
n=3x+1 或 n=3x+2,
如果n=3x+1,则n-1=3x,与①违背,故n≠3x+1;
如果n=3x+2,则n+1=3(x+1),与①违背,故n≠3x+2;
∴假设不成立,即n是3的倍数,又有②得结论:
n是6的倍数。
 
由上面的规律可以推出下面结论:
若x≧1且n=6x-1或n=6x+1不是素数,那么n一定不是2和3的倍数。
证明:
∵n=6x-1或n=6x+1,即n=2(3x)-1或n=2(3x)+1或n=3(2x)-1或n=3(2x)+1。
∴n一定不是2和3的倍数。
 
素数出现规律:
当n≧5时,如果n为素数,那么n mod 6 = 1 或 n mod 6 = 5,即n一定出现在6x(x≥1)两侧。
证明:
当x≥1时,有如下表示方法:
┈┈ 6x,6x+1,6x+2,6x+3,6x+4,6x+5,6(x+1),6(x+1)+1┈┈
不在6x两侧的数为6x+2,6x+3,6x+4,即2(3x+1),3(2x+1),2(3x+2),它们一定不是素数,所以素数一定出现在6x的两侧。
*/
bool isPrime(int num)
{
    if (num == 2 || num == 3)
        return true;
    if (num % 6 != 1 && num % 6 != 5)
        return false;
    for (int i = 5; i*i <= num; i += 6)
        if (num % i == 0 || num % (i+2) == 0)
            return false;
    return true;
}

返回目录:题解目录


分类: OJ题库答案