Как оптимизировать эту программу c, чтобы найти простую факторизацию числа

Question

Я написал код для простой факторизации числа, но я не знаю, как оптимизировать его, чтобы получить лучший результат для больших цифр. У кого-нибудь есть представление о что?

#include<stdio.h> 
int prime(int p, int q, int r); 
int main(){ 
int n,c=0; 
scanf("%d",&n); 
for(int j=2;j<=n;j++){ 
    int t=0; 
    for(int i=1;i<=j;i++){ 
     if(j%i==0){ 
       t++; 
    } 
} 
if(t==2){ //check whether J is prime or not 
    // printf(" %d ",j); 
     c=prime(n,j,0); //check whether j has any factors with N 
     if(c!=0){ 
      printf(" %d ",j); 
      printf(" %d \n",c); 
    } 
} 
} 
return 0; 
} 
int prime(int p,int q,int r){ 
    if(p%q==0){ 
     r++; 
     prime(p/q,q,r); 
    } 
    else{ 
    return r; 
    } 
} 

Answer 1

Ваш код эквивалентен

#include <stdio.h> 

int main(){ 
    int n; 
    scanf("%d", &n); 
    for(int j=2; j <= n; j++) {  // for each j in 2..n, 

     int t=0; 
     for(int i=1; i<=j; i++) { // count j's divisors 
      if(j%i==0) {   // among 1..j 
       t++; 
      } 
     } 

     if(t==2){     // if j is prime: NB! 
      int c=0, nn=n; 
      while(nn%j==0) {  // count multiplicity of j 
       c++;    // as divisor of n, and 
       nn /= j; 
      } 
      if(c!=0){    // report a prime divisor and 
       printf(" %d %d \n", j, c); // its multiplicity 
      } 
     } 
    } 
    return 0; 
} 

но на самом деле все, что требуется, это:

int main(){ 
    int n, c=0; 
    scanf("%d", &n); 
    for(int j=2; j <= n; j++) {  // for each j in 2..n, 

      int c=0; 
      while(n%j==0) {  // if j divides n 
       c++;    // count its multiplicity 
       n /= j;    // while dividing it out of n 
      }      // NB! changing the `n` NB! 
            // which guarantees j is prime 
      if(c!=0){    //  when c != 0 
       printf(" %d %d \n", j, c); 
      } 
    } 
    return 0; 
} 

и поэтому окончательное значительная оптимизация

int main(){ 
    int n, c=0; 
    scanf("%d", &n); 
    for(int j=2; j*j <= n; j++) { // here 

      int c=0; 
      while(n%j==0) { 
       c++; 
       n /= j;    
      } 
      if(c!=0){ 
       printf(" %d %d \n", j, c); 
      } 
    } 
    if(n>1) {      // and here 
     printf(" %d %d \n", n, 1); 
    } 
    return 0; 
} 

Следующая вы можете попытаться найти aw ay, чтобы увеличить j на в основном цикле, чтобы пробежать только по нечетным числам, потому что ни одно число выше может быть простым.