今天做题学会了一个求素数的方法
| 总分 | 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"
#include<stdio.h>
#define q 1000011
int a[q];
int main()
{
printf("please input c,d(c>2):\n");
int i;
int j;
a[]=a[]=;
for(i=;i<q;i++)
{
if(!a[i])
{
for(j=*i;j<q;j+=i)
a[j]=;
}
}
int m,n;
scanf("%d,%d",&n,&m);
int x=n;
int y=m; int z;
z=;
if(m<=)
printf("0\n");
else
{for(i=x+;i<=y;i++)
{
if(!a[i]&&!a[i-])//判断距离是否为2；
{printf("(%ld,%ld)\n",i-,i);
z++;
} }
printf("total=%d\n",z); } }
#define q 1000011
int a[q];
a[]=a[]=;
for(i=;i<q;i++)
{
if(!a[i])
{
for(j=*i;j<q;j+=i)
a[j]=;
}
}
从2开始把每个数的倍数下标的数组设置成值为1
这样一轮循环下来值为0的数组元素，下标值就是素数.
Get到了这个神奇的点，敲起来很快
我原来的做法是这种
public static boolean isPrime(int n){
if (n <= ) {
return n > ;
}
for(int i = ; i < n; i++){
if (n % i == ) {
return false;
}
}
return true;
public static boolean isPrime(int n) {
if (n <= ) {
return n > ;
}
int sqrt = (int)Math.sqrt(n);
for (int i = ; i <= sqrt; i++) {
if(n % i == ) {
return false;
}
}
return true;
public static boolean isPrime(int num) {
if (num <= 3) {
return num > 1;
}
// 不在6的倍数两侧的一定不是质数
if (num % 6 != 1 && num % 6 != 5) {
return false;
}
int sqrt = (int) Math.sqrt(num);
for (int i = 5; i <= sqrt; i += 6) {
if (num % i == 0 || num % (i + 2) == 0) {
return false;
}
}
return true;
}
C语言判断素数（求素数）（两种方法）
素数又称质数。所谓素数是指除了 1 和它本身以外，不能被任何整数整除的数，例如17就是素数，因为它不能被 2~16 的任一整数整除。
思路1)：因此判断一个整数m是否是素数，只需把 m 被 2 ~ m-1 之间的每一个整数去除，如果都不能被整除，那么 m 就是一个素数。
思路2)：另外判断方法还可以简化。m 不必被 2 ~ m-1 之间的每一个整数去除，只需被 2 ~
之间的每一个整数去除就可以了。如果 m 不能被 2 ~
原因：因为如果 m 能被 2 ~ m-1 之间任一整数整除，其二个因子必定有一个小于或等于