View Code of Problem 91

#include<stdio.h>

int prime[10000];

int is_prime(int m){
	if(m==2||m==3){
		return 1;
	}
	if(m%2!=1&&m%2!=5){
		return 0;
	}
	for(int i=5;i<=m/2;i+=6){
		if(m%i==0||m%(i+2)==0){
			return 0;
		}
	}
	return 1;
}
int main(void){
	int m,num[10000];
	scanf("%d",&m);
	int n=0,k=0,x=m;
	for(int i=2;i<=m/2;i++){
		if(is_prime(i)==1){
			prime[n++]=i;
		}
	}
	for(int i=0;i<n;i++){
		if(m<=0){
			break;
		}
		if(m%prime[i]==0){
			num[k++]=prime[i];
			m=m/prime[i];
			i--;
		}
	}
	printf("%d=%d",x,num[0]);
	for(int i=1;i<k;i++){
		printf("*%d",num[i]);
	}
	printf("\n");
}

Double click to view unformatted code.


Back to problem 91