多位数质数的证明关于质数,记得初中的概念,似乎是只可以被1和它本身整除的数.如1357……这些数位较小的,比较容易一眼看出是质数.但是如果是数位较大的,怎么证明它是质数呐?比如在一

Question

多位数质数的证明
关于质数,记得初中的概念,似乎是只可以被1和它本身整除的数.
如1 3 5 7 ……
这些数位较小的,比较容易一眼看出是质数.
但是如果是数位较大的,怎么证明它是质数呐?
比如在一本科普著作上看到一个质数推导公式：n^2-79n+1601
当然这个是错的,在n=80的时候得出的不是质数.
在n=80的时候,得出的是1681.可是我要怎么证,难道一个一个试着乘过去吗?
现在用仅有的高二的知识,很力不从心的样子.
有会高数的人教一教吗?或者告诉我属于什么知识章节的也行.
1楼的您这是什么对待学术的态度哈~
既然质数已经被推到很大的位数了，也该是有方法证的吧。
3楼的前辈谢谢。（鞠躬）那本书上有提到过筛法，但是貌似不是很理解？可以具体谈谈么？
数论貌似是很复杂的纯粹数学的一部份？

Answer 1

首先,现在没有一个既定的公式可以求出完整的质数；
其次,筛选法是通用的方法；
另外,网上到处有30000以内的素数表,可以对比一下；
最后,在excel里面处理,很快就可以得到10万以内的素数.
只要对一个数n开方,取整,对这个整数及其以内的素数做除法,如果都不整除,那就是素数了.
筛选法就是从2开始,后面的数除以这个数,能整除就舍弃,不能就保留,这样无止尽的用下去.比如先保留2,用2去除后面的数,整除舍去,然后看第一个不被2整除的数,就是3,然后用3去除后面的数……
一个整数x内的素数个数大致为x/lnx,没记错的话,是欧拉15岁发现的,拜倒!（当然他13岁就读了大学）