您的位置:首页 >知识精选 >正文

判断是否为素数的方法(判断是否为素数)

摘要 关于判断是否为素数的方法,判断是否为素数不少朋友还不清楚,今天小二来为大家解答以上的问题,现在让我们一起来看看吧!1、关于素数的判

关于判断是否为素数的方法,判断是否为素数不少朋友还不清楚,今天小二来为大家解答以上的问题,现在让我们一起来看看吧!

1、关于素数的判定 所谓“筛选法”指的是“埃拉托色尼(Eratosthenes)筛法”。

2、他是古希腊的著名数学家。

3、他采取的方法是,在一张纸上写上1到100全部整数,然后逐个判断它们是否是素数,找出一个非素数,就把它挖掉,最后剩下的就是素数。

4、 具体做法如下: <1> 先将1挖掉(因为1不是素数)。

5、 <2> 用2去除它后面的各个数,把能被2整除的数挖掉,即把2的倍数挖掉。

6、 <3> 用3去除它后面的各数,把3的倍数挖掉。

7、 <4> 分别用4、5…各数作为除数去除这些数以后的各数。

8、这个过程一直进行到在除数后面的数已全被挖掉为止。

9、例如找1~50的素数,要一直进行到除数为47为止(事实上,可以简化,如果需要找1~n范围内素数表,只需进行到除数为n^2(根号n),取其整数即可。

10、例如对1~50,只需进行到将50^2作为除数即可。

11、) 如上算法可表示为: <1> 挖去1; <2> 用刚才被挖去的数的下一个数p去除p后面各数,把p的倍数挖掉; <3> 检查p是否小于n^2的整数部分(如果n=1000, 则检查p<31?),如果是,则返回(2)继续执行,否则就结束; <4> 纸上剩下的数就是素数。

12、 #include #include int main(void) { int i; int j; int a[101]; // 为直观表示,各元素与下标对应,0号元素不用 for (i = 1; i <= 100; i++) // 数组各元素赋值 a[i] = i; for (i = 2; i < sqrt(100); i++) // 外循环使i作为除数 for (j = i + 1; j <= 100; j++) // 内循环检测除数i之后的数是否为i的倍数 { if (a[i] != 0 && a[j] != 0) // 排除0值元素 if (a[j] % a[i] == 0) a[j] = 0; // i后数若为i的倍数,刚将其置0(挖去) } int n = 0; // 对输出素数计数, 以控制换行显示 for (i = 2; i <= 100; i++) // 输出素数 { if (a[i] != 0) { printf("%-5d", a[i]); // 输出数组中非0元素(未挖去的数) n++; } if (n == 10) { printf(""); // 每行10个输出 n = 0; } } printf(""); return 0; } 运行结果(VC): ================================================= 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 =================================================。

本文到此分享完毕,希望对你有所帮助。

版权声明:本文由用户上传,如有侵权请联系删除!