（c语言）递归＋欧拉筛解法

解题思路:质数通过欧拉筛打表判断，非质数利用递归不断分解到它为质数为止

注意事项:

参考代码

#include<stdio.h>

#include<string.h>

#define maxn 50000

int prime[maxn];

int visit[maxn];

void Prime(int n){   

memset(visit,1,sizeof(visit));

memset(prime,0,sizeof(prime));

int i,j;

int count=0;

for(i=2;i<=n;i++){

if(visit[i]) prime[count++]=i;

for(j=0;j<count&&prime[j]*i<=n;j++){

visit[prime[j]*i]=0;

if(i%prime[j]==0) break;

}

}

}

void primefactor(int num){

if(visit[num]){

printf("%d\n",num);

return ;

}

int i; 

for(i=2;i<num;i++){

if(num%i==0){

printf("%d*",i);

break;

}

}

primefactor(num/i);

}

int main(){

int a,b,i,j;

scanf("%d%d",&a,&b);

Prime(b);

for(i=a;i<=b;i++){

printf("%d=",i);

primefactor(i);

}

return 0;

}

: