初等数论中判断质数的方法

if p≡1 mod3 then 3|(p+2)，很显然p+2是质数，矛盾！

同理p≡2 mod3不成立

p被3整除，p是质数，只能是3

模几是几乎没有定数的，很灵活，一般是一般化，模3，5，7，11等又是题目也会有所暗示，对于二次式，以5为例，你写一下他的完全剩余系，就知道一个数平方后模5只有寥寥几种情况，7也是。有时候3次方要模9（如果需要的话），4次方模16.

但是没有定论，数论就是很灵活的，要活学活用。

质数的判断

试除法： 检查所有可能成为n的因子的数，若没有找到因子，则证明这个数是一个质数

一种朴素的做法就是从2遍历到N-1观察有无N的因子，若没有则说明N为质数，依据的想法是N的因子必然在1~N的范围内