素數分解演算法
㈠ 判定素數的方法有哪些它們的時間復雜度分別是多少(越詳細越好,有高分獎勵)
幾種簡單的判斷素數的方法
素數還有很多東西需要學,先整理三種最簡單的判斷素數的方法,以後再深究補充。
判斷n是否為素數
1、最簡單的方法
用n除以2-sqrt(n),有一個能除盡就不是素數,否則是素數。
時間復雜度:O(sqrt(n))
2、素數判斷法:
這種方法是對上面方法的改進,上面方法是對2-sqrt(n)之間的數進行判斷是否能除盡,而因為有如下算術基本定理,可以減少判斷量。
算術基本定理:又稱為素數的唯一分解定理,即:每個大於1的自然數均可寫為素數的積,而且這些素因子按大小排列之後,寫法僅有一種方式。例如:6936 = 2^3×3×17^2,1200 = 2^4×3×5^2。
由算術基本定理知,任何合數都可分解為一些素數的乘積,所以判斷一個數能不能被2-sqrt(n)之間的素數整除即可。但是必須知道2-sqrt(n)之間的所有素數。
3、篩選法
這種方法可以找出一定范圍內的所有的素數。
思路是,要求10000以內的所有素數,把1-10000這些數都列出來,1不是素數,劃掉;2是素數,所有2的倍數都不是素數,劃掉;取出下一個倖存的數,劃掉它的所有倍數;直到所有倖存的數的倍數都被壞掉為止。
要找出10000以為的所有的素數,則需要一個大小為10000的數組,將其所有元素設置為未標記
首先把1設置為標記,從2開始,標記所有是它倍數的數,然後對下一個沒有標記的數進行標記它的倍數。
當標記完成後,所有未標記的數即為素數。
這種演算法需要O(n)的空間,不要偶數,可以節省一半的存儲空間,標記需要O(n^2/logn)(我寫的,不知道對不對),判斷是否是素數只需要O(1)的時間。
貼一下程序代碼:
/*
2009.5.12 by HK
*/
#include <stdio.h>
#include <math.h>
#include <string.h>
int a[10000];
//100以內的素數
int prime100[] =
{
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,
};
/************************************************************************/
/* 第一種方法:最簡單的方法 */
/************************************************************************/
int is_prime1(int n)
{
if(n % 2 == 0)
return 0;
for(int i=3;i<=sqrt((double)n);i+=2)
if(n % i == 0)
return 0;
return 1;
}
/************************************************************************/
/* 第二種方法:素數判斷法 */
/* 若判斷10000以內的數,需要知道100以內的所有素數 */
/************************************************************************/
int is_prime2(int n)
{
int i;
for(i=0;i<25;i++)
if(n % prime100[i] == 0)
return 0;
return 1;
}
/************************************************************************/
/* 第三種方法:篩選法,打素數表,然後判斷 */
/************************************************************************/
//篩選,a[i]=0,i為素數
void create_table()
{
int i, tmp;
memset(a, 0, sizeof(a));
a[0] = 1;
a[1] = 1;
for(i=2;i<10000;i++)
{
if(!a[i])
{
tmp = i*2;;
while(tmp < 10000)
{
a[tmp] = 1;
tmp += i;
}
}
}
}
int is_prime3(int n)
{
return !a[n];
}
int main()
{
int num, res;
create_table();
printf("Input the num:");
scanf("%d", &num);
res = is_prime3(num);
if(res)
printf("%d is a prime\n", num);
else
printf("%d is not a prime\n", num);
return 0;