求1000以内所有素数并输出的几种方法

这篇具有很好参考价值的文章主要介绍了求1000以内所有素数并输出的几种方法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

今天咱们来点不一样的,来看一下这样的一道题目,他要求我们把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;
}
求1000以内所有素数并输出的几种方法

这样我们的程序就能运行出来了,根本就在于我将他的检测范围由原来的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),有了这个定理,那我们的数据范围就会变得更小,改进如下👇

解法二优化

#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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C语言 五种方法输出100以内的素数(质数) 源码

    目录   写在前面: 输出前20万个素数,对比简单遍历和欧拉筛选的运行时间。 简单遍历: 欧拉筛选: 一、简单遍历 二、遍历至该数的平方根       三、用x/i来代替sqrt(x) 四、朴素筛法 五、埃式筛法 六、欧拉筛法           简单遍历: 3.243秒 欧拉筛选: 0.353秒     

    2024年02月05日
    浏览(61)
  • C语言中判断素数的几种方法

    作为C的初学者们希望大家看看这几种判断素数的方法 既然进来了就看完把 题目要求: 判断n是否为素数。 首先我们讲一下素数的判定:素数就是只能被1或者本身整除的数,这就延伸出了几种不同的判定方法。 方法一:因为判断素数相当于就是判断这个数能不能整除2-这个数

    2024年02月11日
    浏览(46)
  • 在python中查看输出结果的几种方法

    在Python中,查看代码的输出结果通常有多种方法,这取决于你的开发环境、代码结构以及代码运行的上下文。下面列举了一些常见的查看Python代码输出结果的方法,并为每种方法提供了相应的代码示例。  1. 使用 `print()` 语句: `print()` 是最简单直接的输出方法,可以在代码中

    2024年03月18日
    浏览(67)
  • MCU输出日志和调试信息的几种方法

    基于MCU的嵌入式软件开发,可能在某些情况下没有多余存储空间,从而没有在本地有效保存调试和日志信息。 这时,通过某种方式把调试(Debug)和日志(Log)信息输出就显得有意义了。 下面就来讲讲关于嵌入式开发中输出调试和日志信息的几点内容。 标准库 printf 直接输出

    2024年03月15日
    浏览(66)
  • 【Qt】qDebug() 输出16进制数的几种方法

    Qt qDebug() 输出16进制数字的几种方法整理:

    2024年04月28日
    浏览(38)
  • [c语言]求100以内的素数

    (一)、 关于整除算法: 要判断某数是不是质数,不必验证某数m是否被2~m-1的某一个整数整除,只需验证是否被2~sqrt(m)的某一个整数去除就可以了。若只要m被2~sqrt(m)的某个整数整除了,那么它就不是质数。例16能被2,4,8整除,根号16=4,2为2~4之间的一个整数 (二)、

    2024年02月06日
    浏览(44)
  • python的几种输出方式

    1.输出百分比方法 2. print(f “{}”) 的用法 3. .format格式   4. 加号拼接(针对字符串) 扩展知识 -格式化输出 字符 含有 %s 字符串 %d 有符号十进制整数,%06d表示输出的整数显示位数字,不足的地方使用0补全 %f 浮点数,%.02f表示小数点后只显示两位 %% 输出%  %s:代表字符串的占

    2024年04月15日
    浏览(52)
  • 使用筛选法求出 n 以内的素数

    输入描述: 多组输入,每行输入一个正整数(不大于100)。 输出描述: 针对每行输入的整数n,输出两行,第一行,输出n之内(包括n)的素数,用空格分隔, 第二行,输出数组中2之后被清0 的个数。每行输出后换行 筛选法求解过程为:将2~n之间的正整数放在数组内存储,

    2024年02月13日
    浏览(77)
  • chatGPT流式输出的几种方式

    前言 chatGPT是一款高效强大的语言模型,能够给我们的生活带来极大的改变。无论是学习知识还是工作效率,chatGPT都能为我们提供有力的帮助。它可以帮助我们快速获取所需的知识,同时可以帮助我们提高工作效率,包括写文章、文案、推荐策略、生成代码、写周报,流程图

    2024年02月06日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包