素数函数？一个求素数的算法
本文目录
素数函数
你的问题本身就是有问题的。
因为测试一个数字是否是素数，本身就是一个很简单但也很费时的事情。
最简单的正确函数就是：
bool test( 数字 n ){
从2开始到n-1， 对n进行试除；
若某个数字能除净，return false ;
else return true ;
}
这个算法虽然简单，但是有一个致命的弱点。
A：效率低，如果给一个大数字，你自己去算算吧，看你算到猴年马月……
B：计算机上可能无法实现——如果遇到这种情况：数字长度大于了计算机能存储的最大数字。
不过，这个素数算法绝对正确！
然后跟你说些实际的：
1：如果单单考虑不是很变态的素数本身的话，那么早就解决了，而且是目前的一个很好的素数筛选法——厄拉多塞定理就可以。
简而言之，就是从2开始，排除所有2的倍数；然后排除3的倍数；……；以此类推；就这样，当你进行到排除X的倍数的时候，X之前的所有素数你都知道了。
相关的厄拉多塞定理，楼主可以上网去搜，或者《数论》书里有。
2：实际上，计算素数，不可能考虑素数无限大，至少你作为一个个人，即使使用着性能超好的微机，也最多只能考虑有限长度的素数。
现在的计算机是32位，可以计算2^32以内的素数，也就是42亿以内的素数。然后如果拓展了，就可以使用64位，可以计算2^64以内的素数（42亿乘以42亿~自己算范围是多大吧）。由于现在操作系统位数的限制，目前的水准也就是这么多的了。当然啦，如果要确定2^64以内的任意一个数字是不是素数，可就不是这么的用厄拉多塞了，而是用到拉宾-米勒算法和Pollard启发式算法了。具体的参见算法书和某些数论书。
3：大于2^64位的素数，计算机不是不能算。但是时间复杂度要比64位以内的数字要高不是一丁点。这个如果你学了编程就知道了——64位以上的需要数组，而不是单单一个什么整型就能搞定了。
要更长度的，得需要专业领域的人们来解答。
所以，综合而言，
1：类似于你这样很笼统的问素数函数，那么古人就已经很笼统的正确回答了。参考我上面的test()函数以及厄拉多塞定理。
2：真正需要解决的是如何高效地测试某个数字是否是素数，特别是很长的数字。
3：经验教训，就是，数学方面的每个问题都是一个既简单又复杂的问题。门外汉，包括你我，最多也只能研究到和我差不多的这个程度了，很简单吧~但是，那还是一个数学顶尖领域，不过就不是我们普通人能研究能想象的……我现在和你讨论的最长长度是64位二进制，专家们研究的是几千几万长度的二进制和其他优化算法，诸如AKS素数测定算法等……那个算法我是看不懂，很科幻级别。而且，你稍微有一丁点小突破，就可以发包论文并且在这方面树立权威了，就这种程度。
4: 不存在你所谓的“如果没有人知道”，只是有些人不想回答；有些人，像我这样的菜鸟，看着这样的话不大舒服，就来献丑丢脸面。其实，网络虽然是一个虚拟大平台，但也需要大家用心维护，体现出自己的真性情。这么个说法没必要（虽然感觉也蛮正常的）~
一个求素数的算法
t从0到cap^2-1
i从0到cap-1
j从0到i
实际上这里cap起的作用仅仅为了使i和j满足：i从0到cap-1，j从0到i
实际上composite为j从2到i-1时整除i的个数
当j=0时，使composite重置为0
当j=i时，开始判断
每次j能整除i，composite则增加1，到时就不会输出i
当2到i-1的j都不整除i，此时i为素数，composite为0，可以将其输出
希望你能看明白
不懂的话
还可以问的
一般晚上十点我都有空
判断一个数是否为素数的算法
找质数的方法：写出这个数的因数。再判断这个数是质数还是合数。
1、一个数除了1和本身，不再有别的约数，这样的数叫做质数或者素数。例如：2，3，5，7，11，13，17，19，23，29等等。
2、一个数，除了1和本身，还的别的因数，这样的数叫做合数。例如4、8、8、9等等。例如：2的所有因数是1和2两个，所以2是质数。例如6的所有因数是：1，2，3，6。一共是4个，所以6是合数。
找因12的因数：
1×12=12
2×6=12
3×4=12
所以12的因数有：1，2，3，4，6，12。共6个。
找因数的方法可以把这个数分成两个因数相乘的积。从一开始比较容易找，写的时候最好能从小到大写出来。重复的只能写一个。例如9的因数：1×9=9
3×3=9
9的因数是：1，3，9共3个。（重复的3只能写一个。）
求素数算法的数学证明
因为对一个数n，如果他能分解成n=pq，那么pq里必然有一个大于等于根号n一个小于等于根号n，也就是说一个合数必然有一个因子是小于等于根号n的。
所以对一个数n，只要检验他有没有小于等于根号n的因子就可以了
c语言素数的算法
思路如下：
1、求2-n之间的所有素数
2、创建一个数组a[n+2]，其下表为2...n+1
3、数组的功能是记录那些数十素数,其下标表示素数,元素初始化时全为1，表示全部数假设都是素数
4、从2开始往后访问数组的每一个元素，如果这个数十素数就输出，否则往后遍历
5、遍历的同时如果这个数i是素数，则进一步往后将这个数的倍数2*i，3*i，....将这些数都标记为0表示不是素数
6、执行完毕将输出所有素数了
更多文章：
issued retroactively（FORM E上盖“ISSUED RETROACTIVELY”的问题，小女在线等待）
2026年10月15日 10:30
2026年10月15日 10:10
begin和start的区别（start与begin的区别）
2026年10月15日 09:20
vant官网中文（范特365 是韩国化妆品VANT36.5吗）
2026年10月15日 09:10
2026年10月15日 08:10
2026年10月15日 07:30
prison break（越狱（prison break）到底是在讲个什么）
2026年10月15日 06:50
c程序设计第五版教学视频（求C程序设计（第五版）谭浩强教材源代码、视频课件等电子版资料！谢谢大家！）
2026年10月15日 06:40
2026年10月15日 06:20
十六进制转二进制表（16进制转为2进制、8进制、10进制的公式）
2026年10月15日 06:10
