精华内容
下载资源
问答
  • 判断素数最快方法

    2021-05-25 09:36:53
    判断素数最快方法 1、普通方法 bool is_prime(int n) { if (n < 2) return false; int i; for (i = 2; i < n; i++) { if (n % i == 0) { return false; } } return true; } 原理是对每个数进行...

    判断素数最快的方法

    1、普通方法

    bool is_prime(int n)
    {
        if (n < 2)
            return false;
        int i;
        for (i = 2; i < n; i++)
        {
            if (n % i == 0)
            {
                return false;
            }
        }
        return true;
    }
    

    原理是对每个数进行开方,模运算。
    我们来统计0~100000之间有多少素数,并计算程序运行的时间。

    int main()
    {
        clock_t start, finish;
        double totaltime;
        start = clock();
        int n = 0;
        for (int i = 0; i < 100000; i++)
        {
            if (is_prime(i))
            {
                n++;
            }
        }
        cout << "n = " << n << endl;
        finish = clock();
        totaltime = (double)(finish - start) / CLOCKS_PER_SEC;
        cout << "\n此程序的运行时间为" << totaltime << "秒!" << endl;
        return 0;
    }
    

    运行结果如下:

    n = 9592
    此程序的运行时间为1.244秒!
    

    平时需求不太大,勉勉强强能接受这个速度吧。
    但是范围增加到0~1000000,

    for (int i = 0; i < 1000000; i++)
    
    n = 78498
    此程序的运行时间为102.255秒!
    

    这个时间太长了。如果数据量再大一点,那我岂不是要等到天荒地老?

    2、目前我发现的最快的方法

    n>3时,对一个数字进行模6运算,如果结果是0,2,3,4,那么这个数肯定不是素数。

    这样就节省了2/3的工作量。

    接下来和第一种方法类似,不过是从5开始,步长为6,
    除数i和i+2都是奇数并且都是质数,这又减少了特别多的工作量。

    bool is_prime(int num)
    {
        if (num <= 3)
            return num > 1;
        if (num % 6 != 1 && num % 6 != 5)
            return false;
        int s = sqrt(num);
        for (int i = 5; i <= s; i += 6)
            if (num % i == 0 || num % (i + 2) == 0)
                return false;
        return true;
    }
    

    现在运行一下0~100000的结果:

    for (int i = 0; i < 100000; i++)
    
    a = 9592
    此程序的运行时间为0.005秒!
    

    0.005秒,跟1.244秒比,速度是原来的248.8倍。

    接下来

    for (int i = 0; i < 1000000; i++)
    
    n = 78498
    此程序的运行时间为0.064秒!
    

    0.064秒相比于102.255秒,速度增加1597.7倍!简直是一个天上一个地下。

    接下来再增大范围:

    for (int i = 0; i < 10000000; i++)
    
    n = 664579
    此程序的运行时间为1.43秒!
    
    for (int i = 0; i < 100000000; i++)
    
    n = 5761455
    此程序的运行时间为36.375秒!
    

    行了行了,到此为止。

    展开全文
  • 判断素数最快方法

    2020-09-14 14:17:49
    首先判断特殊的,1不是素数,2和3是素数。 其次剩下的所有数都看作是6n、6n+1、6n+2、6n+3、6n+4、6n+5,显然6n、6n+2=2(3n+1)、6n+3=3(2n+1)、6n+4=2(3n+2)都不为素数。所以每六个数的循环中只需判断6n+1和6n+5。 ...

    首先判断特殊的,1不是素数,2和3是素数。

    其次剩下的所有数都看作是6n、6n+1、6n+2、6n+3、6n+4、6n+5,显然6n、6n+2=2(3n+1)、6n+3=3(2n+1)、6n+4=2(3n+2)都不为素数。所以每六个数的循环中只需判断6n+1和6n+5。

    C++代码如下:

    bool isPrime(int n)
    {
        if (n == 1) return false;
        if (n == 2 || n == 3) return true;
        if (n % 6 != 5 && n % 6 != 1) return false;
        float n_sqrt = sqrt(n);
        for (int i = 5; i < n_sqrt; i+=6)
            if (n % i == 0 || n % (i + 2) == 0) return false;
        return true;
    }
    展开全文
  • 判断素数比较方法

    千次阅读 2017-03-06 20:21:55
    public class a{ public static boolean a( int n){ for(int i=2;i if(n%i==0){ return false;  } return true; } } }
    public class a{

    public static boolean a( int n){


    for(int i=2;i<Math.sqrt(n){


    if(n%i==0){

    return false;


                             }


    return true;


    }



    }




    }
    展开全文
  • 快速判断素数方法

    2020-07-10 16:30:19
    做OJ的时候碰到了一个判断素数方法,考虑到素数使用传统暴力方法比较耗时间,所以参考了以下这篇文章,做了个笔记。 https://www.cnblogs.com/IceHowe/p/11186862.html。 常规方法 素数的定义是大于1的自然数中,...

    做OJ的时候碰到了一个判断素数的方法,考虑到素数使用传统暴力方法比较耗时间,所以参考了以下这篇文章,做了个笔记。
    https://www.cnblogs.com/IceHowe/p/11186862.html。

    常规方法

    素数的定义是大于1的自然数中,除了自己本身和1之外,没有其他的因数的数叫做素数或者质数。
    因此常规方法就是将2~N-1的数同时与N相除,如果余数为0,则不是素数。若所有余数都是非0的,那么就是素数。代码我这里就省略了。

    更有效的方法

    定理1:大于5的素数,一定分布在6的倍数左右。例如 5、7;11、13;17、19…
    证明:令x>=1,则所有大于5自然数可以表示为
    …6x-1,6x,6x+1,6x+2,6x+3,6x+4,6x+5,6(x+1),6(x+1)+1,6(x+1)+2…
    上式可以转变成
    …6x-1, 6x, 6x+1, 2(3x+1),3(x+1),2(3x+2),6x+5,6(x+1),6(x+1)+1,2[3(x+1)+1]…
    我们可以看到在6的倍数左边和右边的数都是无法找到其他约束的,而不在6x左右两侧的数6x+2,6x+3,6x+4都可以被2、3、2整除。
    定理2:一个数若可以进行因数分解,那么分解时得到的两个数一定是一个小于等于sqrt(n),一个大于等于sqrt(n)
    因此我们遍历的时候,只需要遍历到小于等于sqrt(n)一侧,如果这一边没有出现因数的话,那么在大于等于sqrt(n)的一侧一定不会出现因数。
    因此C++代码如下

    #include<iostream>
    #include<math.h>
    bool prime(int num)
    {
    	if(num==2 || num==3) 
    	return true;
    	if(num%6!=1 &&num%6!=5)
    	return false;
    
    	int temp;
    	temp=int(sqrt(float(num)));
    	for(int i=5;i<=temp;i+=6)
    	{
    	if(num%i==0 || num%(i+2)==0) 
    	return false;
    	}
    return true;
    }
    
    展开全文
  • 素数 (20分) 令Pi 表示第i个素数。现任给两个正整数M≤N≤104 ,请输出PM 到PN 的所有素数。 输入格式: 输入在一行中给出M和N,其间以空格分隔。 输出格式: 输出从PM 到PN 的所有素数,每 10 个数字占 1 行...
  • 判断素数方法

    2016-03-30 08:38:11
    个人常用判断素数方式: bool prime(int n) { if(n) return false; for(int i=2;i;i++) if(n%i==0) return false; return true; } 相对而言,速度较些的写法: bool prime(int n) { if(n) return fal
  • 判断质数 素数——我知道的最快方法.pdf
  • 本题的关键是输出素数,素数又叫质数,指在大于1的自然数中,除了1和它本身以外不再有其他因数的自然数,必须为正整数,1和0既非素数也非合数,所以在写判断素数的函数时 第一步首先判断给的数是否大于2,若小于2,...
  • 最快、最合适地判断一个数为素数 说明 分为打表法和单个判断法两类方法 打表法是开始时将所有素数标记出来,适合多次调用判断 单个判断法则是只一个数一个数判断,适合少量判断来节省时间,以及某些其他作用 打...
  • 快速判断素数
  • 判断素数的几种方法

    千次阅读 多人点赞 2018-12-19 15:40:51
    设计程序判断素数,经过总结,有如下常见方法: 方法一: #include&amp;lt;stdio.h&amp;gt; int main() { int x=0,isprime=1; scanf(&quot;%d&quot;,&amp;amp;x); for(int i=2;i&amp;...
  • 判断素数最有效的算法

    万次阅读 多人点赞 2018-06-25 17:22:27
    2 有效方法判断 3 测试 定义 约数只有1和本身的整数称为质数,或称素数。   1 常规方法判断 根据定义,因为质数除了1和本身之外没有其他约数,所以判断n是否为质数,根据定义直接判断从2到n-1是否存在n的...
  • Java中判断素数的五种方法

    万次阅读 多人点赞 2019-01-21 17:04:41
    Java 中判断素数我们有很多方法,每种方法时间复杂度也不一样。今天我汇总了一下,分享给大家。既可以输出前 50 或 n 个素数,也可以判断 100 (或 n) 以内的素数。 1. 从 2 到 x-1 测试是否可以整除 Scanner in = ...
  • 素数的快速判断方法

    千次阅读 2019-05-25 12:30:38
    原理:大于等于5的素数与6的倍数相邻 证明 所有自然数可以用集合A = { 6n, 6n+1, 6n+2, 6n+3, 6n+4, 6n+5 }表示,其中 n >= 0,显然,子集B = {6n, 6n+2, 6n+3, 6n+4}内的元素都不是素数,所以只有6n+1和6n+5可能...
  • 判断质数/素数——我知道的最快方法

    万次阅读 多人点赞 2017-12-01 20:23:32
    标准版:大部分人都知道的比较方法判断从2到sqrt(n)是否存在其约数,时间复杂度O(sqrt(n)) 高配版:判断2之后,就可以判断从3到sqrt(n)之间的奇数了,无需再判断之间的偶数,时间复杂度O(sqrt(n)/2) 尊享...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 11,060
精华内容 4,424
关键字:

判断素数最快方法