素数是非常简单的一个概念,所谓素数,是指恰好有2个约数
的整数,那么这两个数就是它本身和1。
素数的判定方法有这么几种,
(1)简单判定,
(2)飞马测试
(3)r 算法
(4)数域筛法
(5) 埃式筛法
(6)区间筛法
那么先从最简单的判素方法学起~~~
1.素性测试
给定整数n,请判断n是不是素数
# include<stdio.h> bool is_prime( int n ) { for ( int i = 2;i*i <= n;i++ ) { if ( n%i == 0 ) return false; } return n!=1; } int main(void) { int n; scanf("%d",&n); if(is_prime(n)) printf("Yes\n"); else printf("No\n"); return 0; }
在此,对这个公式做一个简要的证明,如果d是n的约数(n%d == 0),
那么n/d也是n的约数(n%(n/d) == 0)。用n = d*n/d 可以推出来
sqrt(n)>= min ( d, n/d ), 那么我们就可以将原先的[ 2,n-1 ]
的区间问题转化到 [ 2,sqrt(n)],并且该算法的世间复杂度为 O(sqrt(n))