密码学求素数及素数分解

2022-07-31 05:58:10 文档大全网 [ 字体：小中大 ] [ 阅读： ]

【#文档大全网# 导语】以下是®文档大全网的小编为您整理的《密码学求素数及素数分解》，欢迎阅读！
素数,密码学,分解
密码学求素数及素数分解

 求素数

#include #include IsPrime(int value ) {

int i;

/* if(value ==1) return 0;*/

for(i=2;i<=sqrt(value);i++) {

if(value %i==0) return 0; }

return 1; }

void main() { int n;

for(n=1;n<=200;n++) {

if(IsPrime(n))

printf("%d is a prime!\n",n); else

printf("%d is not a prime!\n",n); } } O（n）

2、将整数分解成素数相乘

#include #include

//判读是否为质数，并带回它的最小因数（除1之外）。 int IsPrime(int value) {

int i;

for (i=2;i {

if ((value%i)==0)

return 0; }

return 1; }

//递归调用，如果为质数则打印出来，否则将该数除以它的最小因数（除1之外）后递归调用

void PrimeSubmultiple(int value) {

int submultiple;

if (IsPrime(value,&submultiple)) {

printf("%d",value); return; } else {

printf("%d*",submultiple);

PrimeSubmultiple(value/submultiple); return; } }

int main() {

int x;

printf("\nPlease input a integar:"); scanf("%d",&x); printf("%d=",x);

PrimeSubmultiple(x);

} O（n）