今天咱们来点不一样的,来看一下这样的一道题目,他要求我们把1-1000的素数全部找到并且输出
那我们先要了解什么是素数,所谓素数,就是指在大于1的自然数中,除了1和它本身以外不再有其他因数的自然数。而合数则恰巧与素数相反,是指在大于1的整数中除了能被1和本身整除外,还能被其他数(0除外)整除的数
解法一
那我们根据定义解法一就得出来了,那就是从2开始到1000进行遍历,然后一个一个确认它除了1和它本身还有没有其他的因子,然后大家都知道2是最小的素数,而2以外的正偶数都是合数,所以咱们可以对它进行一些小的改进和优化👇
#include <iostream>
#include <iomanip> //setw()对应的头文件
using namespace std;
int main ()
{
int n,i;
bool k= false ; //设置布尔类型的变量以方便进行对素数的标记
cout << setw(5) << 2 ; //2是最小的素数
for(n=3;n<1001;n+=2){
k=true;
for(i=2;i<n;i++){
if(n%i==0){
k= false ;
break; //是合数就跳出循环
}
}
if(k){ //由标记决定是否为素数
cout << setw(5) << n ; //输出进行格式化,以便查看
}
}
return 0;
}
通过这个方法是可以做出这道题目的,但是放在洛谷或者学校的oj网站上却老是WA,这又是为什么呢,其实是我们的程序运行太过复杂,它的时间复杂度为O(n),这是很容易使整个程序崩溃的,所以我们一定要学会对自己的算法进行优化,降低它的时间复杂度和空间复杂度
优化如下👇
解法一优化
#include <iostream>
#include <iomanip>
using namespace std;
int main ()
{
int n,i;
bool k= false ;
cout << setw(5) << 2 ;
for(n=3;n<1001;n+=2){
k=true;
for(i=2;i<=n/i;i++){ //将i的范围大大缩小
if(n%i==0){
k= false ;
break;
}
}
if(k){
cout << setw(5) << n ;
}
}
return 0;
}
这样我们的程序就能运行出来了,根本就在于我将他的检测范围由原来的n变成了sqrt(n),也就是n的开方,那它的时间复杂度自然也从O(n)---变成了---->O(sqrt(n))
以上是我们的解法一,接下来介绍一种素数筛查法
解法二
所谓素数筛查法,顾名思义就是要通过筛掉合数的方法来找出素数。
这里有一个定理要介绍给大家:一个合数一定能够写成若干个素数之积的形式。那么我们就只需要把2的倍数找出来扔掉,3的倍数找出来扔掉,5的倍数找出来扔掉,7的倍数找出来扔掉,11的倍数找出来扔掉……以此类推,直到这个素数是小于等于n开方的最大素数就OK了
然后思路明白了,大家拿代码实现就好了。首先要扔掉那就要先存起来,那就要用到数组这个东西,这样的话我们只需要将合数变成0,素数留下,最后遍历数组的时候判断一下就OK了。
但是值得大家注意的一点是:这几个素数因子也会被判断为合数,故此我们要提前输出这几个素数因子以保证它的完整性
#include <iostream>
#include <iomanip>
using namespace std;
int main()
{
int a[1001]={0};
int i;
cout << setw(5) << 2 << setw(5) << 3 << setw(5) << 5 << setw(5) << 7 ;
cout << setw(5) << 11 << setw(5) << 13 << setw(5) << 17<< setw(5) << 19 ;
cout << setw(5) << 23 << setw(5) << 29 << setw(5) << 31 ;
//这是在保证完整性!!!(放不下就写下一行了)
for(i=3;i<1001;i++){
if(i%2!=0&&i%3!=0&&i%5!=0&&i%7!=0&&i%11!=0&&i%13!=0&&i%17!=0&&i%19!=0&&i%23!=0&&i%29!=0&&i%31!=0)
a[i]=i; //是质数才输入,否则就是初始化的0
}
for(i=0;i<1001;i++){
if(a[i]!=0) //判断是否为素数
cout << setw(5) << a[i] ;
}
return 0;
}
对于这个解法的优化方法,我们还要用到另一个定理——从5开始,素数一定在6的倍数周围(只比它大1或小1),有了这个定理,那我们的数据范围就会变得更小,改进如下👇文章来源:https://www.toymoban.com/news/detail-457459.html
解法二优化
#include <iostream>
using namespace std;
#include <iomanip>
int isPrime (int a); //声明一个新的函数来判断是否为素数
int main()
{
int a,b,i;
cout << setw(5) << 2 << setw(5) << 3 << setw(5) << 5 << setw(5) << 7 ;
cout << setw(5) << 11 << setw(5) << 13 << setw(5) << 17<< setw(5) << 19 ;
cout << setw(5) << 23 << setw(5) << 29 << setw(5) << 31 ;
for(i=6;i<167;i++){
a=6*i-1;
b=6*i+1;
if(isPrime (a))
cout << setw(5) << isPrime (a) ; //返回了非零数字就输出
if(isPrime (b))
cout << setw(5) << isPrime (b) ; //返回了非零数字就输出
}
return 0;
}
int isPrime (int a)
{
if(a%2!=0&&a%3!=0&&a%5!=0&&a%7!=0&&a%11!=0&&a%13!=0&&a%17!=0&&a%19!=0&&a%23!=0&&a%29!=0&&a%31!=0)
return a ; //如果为素数返回此数
else
return false ; //如果为合数终止程序
}
这就是查找素数的方法,还有一种运用费马小定理的解法,那个方法只能保证找到的数字大概率是素数,不能够百分百的保证,所以暂时先不给大家介绍误导大家了。希望以上的解法对大家有所帮助,谢谢大家的阅读~~~文章来源地址https://www.toymoban.com/news/detail-457459.html
到了这里,关于求1000以内所有素数并输出的几种方法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!