发布日期:2016-01-05 16:38 来源: 标签: 编程语言 开发语言 C++入门教程 C++判断素数算法
本章我们主要学习C++中判断素数的算法,下面我们就做一下具体讲解,希望大家多多支持中国站长网络学院。
这是一个基本的算法编程问题,即给定一个整数x,判断x是否为素数。算法基本思路如下:让x被2到sqrt(x)除,如果x能被2至sqrt(x)之中任何一个整数整除,那么说明x不是质数,否则是质数。原因不再说明,具体代码如下:
#include <cmath>
bool IsPrime(int x)
{
    for(int i = 2; i <= (int)sqrt(x); i++)
    {
        if((x % i) == 0)
            return false;
    }
    return true;
}
继续引申,从1开始的连续整数中哪些为素数?可以使用“筛选法”。所谓“筛选法”指的是“埃拉托色尼(Eratosthenes)筛法”。他是古希腊的著名数学家。他采取的方法是,在一张纸上写上1到100全部整数,然后逐个判断它们是否是素数,找出一个非素数,就把它挖掉,最后剩下的就是素数。具体做法如下:
<1> 先将1挖掉(因为1不是素数)。
<2> 用2去除它后面的各个数,把能被2整除的数挖掉,即把2的倍数挖掉。
<3> 用3去除它后面的各数,把3的倍数挖掉。
<4> 分别用4、5…各数作为除数去除这些数以后的各数。这个过程一直进行到在除数后面的数已全被挖掉为止。例如找1~50的素数,要一直进行到除数为47为止(事实上,可以简化,如果需要找1~n范围内素数表,只需进行到除数为n^2(根号n),取其整数即可。例如对1~50,只需进行到将50^2作为除数即可。)
如上算法可表示为:
#include <iostream>
#include <cmath>
//#include "Prime.h"
int main()
{
    int array[101];
        int i, j;
    for(i = 2; i <= 100; i++)
        array[i] = i;
    for(i = 2; i < (int)sqrt(100); i++)
    {
        if(array[i] != 0)
        {
            for(j = i + 1; j <= 100; j++)
            {
                if((array[j] != 0) && (array[j] % array[i] == 0))
                {
                    array[j] = 0;
                }
            }
        }
    }
    for(i = 2; i <= 100; i++)
    {
        if(array[i] != 0)
            std::cout << array[i] << std::endl;
    }
    return 0;
}
上述的筛选法的时间复杂度为O(sqrt(n)*n),效果不够理想。

相关评论

专题信息
    Visual C++是一个功能强大的可视化软件开发工具,是高等院校计算机及相关专业主要核心课程。 本教程对Visual C++ 的应用与开发进行了详细系统的介绍,内容主要包括:Visual C++程序的建立,菜单、工具栏和状态栏的创建,对话框和常用控件,窗口、文档与视图,图形绘制,数据库应用,多媒体技术等。 本教程以案例教学为主,各章节都附有大量的实例,并且操作步骤详细,有利于引导读者更好的消化、理解和实际应用本章节所学的知识内容,希望大家能多多支持中国站长网络学院!