判断素数的几种方法思考(转)
【】判断素数是经常遇到的问题,下面就总结几种方法
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
分享到:
相关推荐
试除法是最直观的方法,即对每个待判断的数字n,从2到√n遍历所有可能的因子,如果发现因子,则n不是素数。这种方法虽然简单,但对于大数来说效率较低。而埃拉托斯特尼筛法则是一种更有效的筛选方法,通过依次剔除...
从给定的文件标题、描述、标签以及部分内容中,我们可以提炼出与C语言程序设计、算法思考及计算机等级考试相关的几个关键知识点: ### C语言基础知识 C语言是一种结构化编程语言,广泛应用于系统编程和嵌入式开发...
每个合数都能唯一地表示为几个素数的乘积,这些素数被称为该合数的素因数。分解素因数有助于理解和简化复杂的数字结构。课程中提到了两种分解素因数的方法:“树枝分解法”和“短除法”。前者通过逐步分解直至不能再...
本课件主要介绍了几种常见的流程控制结构,包括while循环、do...while循环、foreach循环、循环的嵌套、跳转语句(如goto、break、continue、return、throw)以及异常处理。 首先,while循环是一种先测试型循环,它...
作者提出,首次授课应当在机房进行,利用实际有趣的程序案例(如猜数字游戏、猴子吃桃问题、一元二次方程求解程序、判断素数等)来吸引学生,并鼓励他们运行自己的第一个C程序,从而让学生认识到编程的乐趣和实用性...
例如,在讲解如何判断一个数是否为素数时,教师可以先从传统思路出发,然后引导学生思考算法的改进方法,比如减少除数范围,最终理解为何使用从2到sqrt(n)的范围进行判断。 最后,适当利用多媒体教学手段。由于过去...
这份名为"Ch程序流程控制实用PPT学习教案.pptx"的资料详细介绍了几种常见的流程控制结构,包括while循环、do...while循环、foreach循环、循环的嵌套以及跳转语句,同时也涉及到return语句和异常处理。以下是对这些...
【Java实验1-9.docx】的实验主要涵盖了Java的基础知识,...实验思考题涉及了更深层次的Java知识,如类和对象的关系、访问控制修饰符的作用、构造方法、继承机制、静态属性和方法等,这些都是Java编程基础中的关键概念。
在准备NOIP复赛的过程中,有几个关键的学习方法和知识点需要掌握,以提高竞争力。 首先,选择合适的编程语言至关重要。NOIP比赛支持C/C++和Pascal三种语言。如果你没有编程基础,建议从Pascal开始,因为它相对容易...
例如,你可能会在这些源代码中看到以下几种类型的题目: 1. **排序算法**:如冒泡排序、插入排序、选择排序、快速排序、归并排序等,这些都是理解数据结构和算法的基础。 2. **搜索算法**:包括线性搜索和二分搜索...
- **合数判断函数** `su(long m)`:与之前判断素数类似,但在这里用于判断合数。 - **主函数** `main()`:使用数组 `a` 来存储连续的合数。通过循环结构不断检查每个自然数是否为合数,并将符合条件的合数存储到数组...
- **1.2.6 示例:素性测试**: 介绍一种高效判断素数的方法。 - **1.3 使用高阶过程形成抽象** - **1.3.1 作为参数的过程**: 如何将过程作为其他过程的参数。 - **1.3.2 使用lambda构造过程**: 学习lambda表达式...
本篇文章将重点讨论其中的几个关键知识点,包括波利亚计数法(Polya Enumeration Theorem)、伯恩赛德引理(Burnside's Lemma)、置换群及其运算、素数理论以及欧拉函数。 1. 波利亚计数法和伯恩赛德引理: 这两个概念...
VB常用算法总结主要涵盖了几种基础的编程算法,包括累加与连乘、求素数、穷举法以及递推法。这些算法是编程解决问题的基础工具,尤其在VB这种面向对象编程语言中,理解并掌握这些算法对于编写高效且准确的代码至关...
筛选法,如埃拉托斯特尼筛法,是一种有效的找出所有小于给定数的质数的方法,通过去除每个质数的倍数来逐步筛选。 6. **数的奇偶性**:数的奇偶性是另一个相关的概念,主要涉及两个数相加的结果是奇数还是偶数。若...
以下是几种常用的构建反例的方法: 1. **直接构造法**:直接根据命题条件构建一个具体的例子,使其不满足命题的结论。 - **例3**:假设命题为“所有偶数都可以表示为两个素数之和”。一个著名的未解决问题是...
而打印N以内的素数程序中,可以优化算法,例如使用Sieve of Eratosthenes方法来更高效地找出素数。 通过这些例子,我们可以看到VBA的强大之处在于它可以方便地与Excel等Office应用程序集成,进行复杂的计算、数据...
10. 素数判断:第20题求素数,需要掌握素数的基本性质和筛选方法,如埃拉托斯特尼筛法。 11. 二维数组与矩阵操作:如第11题的数组置零,第13题的求每列最小值,第14题的求周边元素和,第15题的提取数字的后几位,...
这两种算法都是基础的排序方法,选择排序每次从未排序的部分选出最小(或最大)的元素,冒泡排序则通过重复比较相邻元素来排序。 以上算法不仅涵盖了C程序设计中的基本概念,如数组、循环、条件语句等,同时也涉及...