判决素数个数

发布时间:2023年12月22日

题目描述

求?X,Y?之间的素数个数(包括?X?和?Y)。

输入格式

两个整数?X?和?Y(1≤X,Y≤1.1×106)。

输出格式

输出一个整数,表示?X,Y?之间的素数个数(包括?X?和?Y)。

输入输出样例

输入 #1

1 100

输出 #1

25

这道题他说要判断素数,而众所周知,判断素数基本上都要用埃氏筛选法:

埃拉托斯特尼筛法,简称埃氏筛或爱氏筛,是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。要得到自然数n以内的全部素数,必须把不大于根号n的所有素数的倍数剔除,剩下的就是素数。

c++埃氏筛选法:

bool a[10005];
	for(int i=2;i<=y;i++)//记得一定要从2开始
        if(a[i])
            for(int j=2;j*i<=y;j++)
                a[j*i]=false;//如果不是算数,那么赋值为false 

?所以,代码!!!

#include<bits/stdc++.h>
using namespace std;
int x,y,sum=0;
bool is[1000001];
int main(){
    cin>>x>>y;
    if(x>y)swap(x,y);
    memset(is,true,sizeof(is));
    is[0]=is[1]=false;
    for(int i=2;i<=y;i++)if(is[i])for(int j=2;j*i<=y;j++)is[j*i]=false;
    for(int i=x;i<=y;i++)if(is[i])sum++;
    cout<<sum;
    return 0;
}

其他方法:

#include <bits/stdc++.h>
using namespace std;
int main()
{
	long long x,y,sum=0;
	cin >> x >> y;
	if(x>y)
		swap(x,y);
	for(int i=x;i<=y;i++)
	{
		bool q=1;
		for(int j=2;j<=sqrt(i);j++)
			if(i%j==0)
			{
				q=0;
				break;
			}
		if(q&&i!=1)
			sum++;
	}
	cout << sum << endl;
	return 0;
}

?

文章来源:https://blog.csdn.net/Dream_MC_LZR/article/details/135150295
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。