今天做题学会了一个求素数的方法

总分 13

 

孪生素数
相差为2的两个素数称为孪生素数。例如，3与5，41与43等都是孪生素数。设计程序求出指定区间上的所有孪生素数对。区间上限和下限由键盘获取。
程序运行示例如下：
please input c,d(c>2):
10,200↙
(11,13)
(17,19)
(29,31)
(41,43)
(59,61)
(71,73)
(101,103)
(107,109)
(137,139)
(149,151)
(179,181)
(191,193)
(197,199)
total=13

输入格式:
区间上限和下限的输入格式： "%ld,%ld"

输出格式：
区间上限和下限的输入提示信息："please input c,d(c>2):\n"
孪生素数的输出格式："(%ld,%ld)\n"
所有孪生素数对的总数输出格式： "total=%d\n"
 1 #include<stdio.h>
 2 #define q 1000011
 3 int a[q];
 4 int main()
 5 {
 6     printf("please input c,d(c>2):\n");
 7     int i;
 8     int j;
 9     a[1]=a[0]=1;
10     for(i=2;i<q;i++)
11     {
12         if(!a[i])
13         {
14         for(j=2*i;j<q;j+=i)
15             a[j]=1;
16         }
17     }
18     int m,n;
19     scanf("%d,%d",&n,&m);
20     int x=n;
21     int y=m;
22      
23      
24         int z;
25         z=0;
26         if(m<=2)
27             printf("0\n");
28         else
29         {for(i=x+2;i<=y;i++)
30         {
31             if(!a[i]&&!a[i-2])//判断距离是否为2；
32             {printf("(%ld,%ld)\n",i-2,i);
33                 z++;
34             }
35             
36         }
37         printf("total=%d\n",z);
38   
39         }
40      
41 }

 

 

从这个博客学到了一个求素数的方法

 

#define q 1000011
int a[q];  
a[1]=a[0]=1;
    for(i=2;i<q;i++)
    {
        if(!a[i])
        {
        for(j=2*i;j<q;j+=i)
            a[j]=1;
        }
    }

 

从2开始把每个数的倍数下标的数组设置成值为1

这样一轮循环下来值为0的数组元素，下标值就是素数.

Get到了这个神奇的点，敲起来很快

我原来的做法是这种

（转载的他人的代码）

 1 public static boolean isPrime(int n){
 2     if (n <= 3) {
 3         return n > 1;
 4     }
 5     for(int i = 2; i < n; i++){
 6         if (n % i == 0) {
 7             return false;
 8         }
 9     }
10     return true;
 1 public static boolean isPrime(int n) {
 2     if (n <= 3) {
 3         return n > 1;
 4     }
 5     int sqrt = (int)Math.sqrt(n);
 6     for (int i = 2; i <= sqrt; i++) {
 7         if(n % i == 0) {
 8             return false;
 9         }
10     }
11     return true;
 1 public static boolean isPrime(int num) {
 2     if (num <= 3) {
 3         return num > 1;
 4     }
 5     // 不在6的倍数两侧的一定不是质数
 6     if (num % 6 != 1 && num % 6 != 5) {
 7         return false;
 8     }
 9     int sqrt = (int) Math.sqrt(num);
10     for (int i = 5; i <= sqrt; i += 6) {
11         if (num % i == 0 || num % (i + 2) == 0) {
12             return false;
13         }
14     }
15     return true;
16 }

 

C语言判断素数（求素数）（两种方法）

 

素数又称质数。所谓素数是指除了 1 和它本身以外，不能被任何整数整除的数，例如17就是素数，因为它不能被 2~16 的任一整数整除。

思路1)：因此判断一个整数m是否是素数，只需把 m 被 2 ~ m-1 之间的每一个整数去除，如果都不能被整除，那么 m 就是一个素数。

思路2)：另外判断方法还可以简化。m 不必被 2 ~ m-1 之间的每一个整数去除，只需被 2 ~  之间的每一个整数去除就可以了。如果 m 不能被 2 ~  间任一整数整除，m 必定是素数。例如判别 17 是是否为素数，只需使 17 被 2~4 之间的每一个整数去除，由于都不能整除，可以判定 17 是素数。

原因：因为如果 m 能被 2 ~ m-1 之间任一整数整除，其二个因子必定有一个小于或等于 ，另一个大于或等于 。例如 16 能被 2、4、8 整除，16=2*8，2 小于 4，8 大于 4，16=4*4，4=√16，因此只需判定在 2~4 之间有无因子即可。