判断素数的几种方法思考(转)
【】判断素数是经常遇到的问题,下面就总结几种方法
1、最简单的从2~sqrt(N)的方法(N>=2,下同)
2、筛选法
3、素数判断法
概念说明:
素数,又叫质数,指除了1和它本身外,没有其他因数。(如果你不知道什么叫因数,建议你去从小学2年级开始学习-_-!);
合数:自然就是除了1和它本身外有其他因数。
需指出一点,1既不是质数也不是合数。
因此,判断N是素数的简单而笨的方法就是看看N有没有因数。
1、最简单的方法:
该算法的思想就是用2~sqrt(N),依次去对N求余,只要有一个余数是0,则N是合数。举例如下:
1/**//*-------------isPrimer.c-------------
2 *----------Date : 09-25-2005---------
3 *----------All Rights Shared---------
4 *----------test in C-Free3.5---------
5 *-----------------------------------*/
6
7#include <stdio.h>
8#include <stdlib.h>
9#include <math.h>
10
11void main(int argc, char* argv[])
12{
13 int N, i, m,flag = 0;
14 if(argc < 2)
15 {
16 while(1)
17 {
18 printf("Please input a non-integer:");
19 if(scanf("%d", &N) != 1)
20 {
21 fflush(stdin);
22 continue;
23 }
24 break;
25 }
26 }
27 else
28 N = atoi(argv[1]);
29 m =(int) sqrt(N*1.0);
30 for(i = 2;i <= m; i++)
31 if(N % i ==0)
32 {
33 flag = 1;
34 break;
35 }
36 if(flag)
37 printf("%d is not a primer\n", N);
38 else
39 printf("%d is a primer\n", N);
40 system("pause");
41}
注:以上代码判断不出1、2、3来。
上面的代码就是按照这个简单的思路来的,思路是简单了,但是方法效率是不高的。因为我们知道,一个数如果不能被2整除,那么也就不能被4、6、等所有的偶数整除。但是我们的程序在判断了2之后依然会去判断4、6等。所以我们可以把循环规则改变成先判断2,如果不能被2整除就从3开始判断所有的奇数。即:
1 if(N % 2 != 0)
2 {
3 for( i = 3; i <= m; i +=2)
4 //……此处省略了
5 }
6 else
7 // 合数
2、筛选法判断素数。
这个方法不是用来判断一个素数,而是所有素数的方法。方法的原理是:
2、筛选法判断素数。
这个方法不是用来判断一个素数,而是所有素数的方法。方法的原理是:
[quote]
http://www.math.utah.edu/classes/216/assignment-07.html
The goal of this assignment is to design a program which will produce lists of prime numbers. The method is based on the one discovered by Erastosthenes (276 - 196 BC). His method goes like this. First, write down a list of integers
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Then mark all multiples of 2:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
x x x x x x x x x
Move to the next unmarked number, which in this case is 3, then mark all its multiples:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
x x x x x x x x x x x
Continue in this fashion, marking all multiples of the next unmarked number until there are no new unmarked numbers. The numbers which survive this marking process (the Sieve of Eratosthenses) are primes. (You should complete this marking process yourself).
The new part of the C language that you will have to learn in order to do this program is the array.
[/quote]
这段E文没什么难理解的,就是首先生成数组,然后从第一个开始依次标注它的倍数,然后从下一个没有被标注的开始,标注它所有的倍数,这样依次下去,最后没有被标注的都是素数。下面是代码:
1 /*----------------------------------------
2 *--------------筛选法--------------------
3 *---------------------------------------*/
4 #include <stdio.h>
5 #include <stdlib.h>
6
7 void main(int argc, char* argv[])
8 {
9 int N, i, *m, j = 0,temp;
10 if(argc < 2)
11 {
12 while(1)
13 {
14 printf("Please input a non-integer:");
15 if(scanf("%d", &N) != 1)
16 {
17 fflush(stdin);
18 continue;
19 } /* end if*/
20 break;
21 } /*end while*/
22 } /* end if*/
23 else
24 N = atoi(argv[1]);
25 m = (int*)malloc(sizeof(int) * (N - 1));
26 // inital the arry
27 for(i = 0; i < N -1; i++)
28 *(m+i) = i+2;
29 while(1)
30 {
31 // find the start number-index
32 for(; j < N - 2;j++)
33 if(*(m+j) != 0){temp = *(m+j);break;}
34
35 if(j < N - 2)
36 {
37 for(i = j+1; i < N - 1; i++)
38 if(*(m+i) % temp == 0)
39 *(m+i) = 0;
40 } /* end if*/
41 else break;
42 j++;
43 } /* end while*/
44 printf("The primer is:");
45 for(i = 0; i < N-1; i++)
46 if(*(m+i) != 0)printf("%d,", *(m+i));
47 printf("\n");
48 free(m);
49 system("pause");
50 } /* end main */
当然这样占用的空间是相当大的。另外,其实可以省略所有的偶数。
3、素数判断法【简单方法】
考虑到这么一个现实:任何一个合数都可以表现为适当个素数的乘积的形式,所以我们只用素数去除要判断的数即可,比如要判断100以内的素数,只用2,3,5,7就够了,10000以内的数用100以内的素数判断足以。
1/**//*------------------------------------------
2 *---------------------100以内的素数-------
3 *-----------------------------------------*/
4#include <stdio.h>
5#include <stdlib.h>
6
7void main(int argc, char* argv[])
8{
9 int N, i, j = 0,size;
10 int a[] = {2,3,5,7};
11 if(argc < 2)
12 {
13 while(1)
14 {
15 printf("Please input a non-integer:");
16 if(scanf("%d", &N) != 1)
17 {
18 fflush(stdin);
19 continue;
20 } /**//* end if*/
21 break;
22 } /**//*end while*/
23 } /**//* end if*/
24 else
25 N = atoi(argv[1]);
26 size = sizeof(a) / sizeof(int);
27 printf("The primer is:");
28 for(i =2; i < N; i++)
29 {
30 for(j = 0; j < size; j++)
31
分享到:
相关推荐
ACM的素数判断,包括米勒拉宾伪素数判定,筛选法。
多种方法判断素数
python判断素数的几种方式
素数判断的几种方法代码实现及其复杂度分析.pdf
c++判断素数,很简单的程序,具体的自己看
c#版的判断素数,可以在当前框输入数字,也可以在新建的窗口输入,再进行素数合数的判断
判断素数的方法汇总:1.常见方法的讲述及代码,常见方法的优化的讲解及代码。2.筛选法的方法及代码。3.6素数法的方法及代码。
判断素数.cpp
摘要:C#源码,算法相关,素数 使用C#判断素数的一个实例程序源代码,在输入框内输入任意数字,即可立即判断出该数值是否为素数,源代码开源,对学习C#中的算法有益。
判断素数(sqrt).cpp
简单方法判断素数
c语言codeblocks简单的判断素数功能实现
这是一个c语言判断素数的问题 我自己也研究了 。
教你如何判断素数,理解算法结构
C语言程序设计-程序举例判断素数.pptx
不同素数判定方法及C语言代码实现,分析各种方法的事件复杂度,适用于大数处理。
判断一个数是否为素数
java中用于判断素数的程序。大家可以看看。
判断素数,只能被1或本身整除的数称为素数 基本思想:把m作为被除数,将2—INT( )作为除数,如果都除不尽,m就是素数,否则就不是。(可用以下程序段实现)