hdu 1164 Eddy's research I 素数筛选法

蔚落 2021-11-02 14:28 176阅读 0赞

1 #include <stdio.h>
     2 #include <string.h>
     3 #include <stdlib.h>
     4 #include <math.h>
     5 
     6 int A[80000], dp[20000];
     7 
     8 const int inf = 65535;
     9 
    10 int prime( )
    11 {
          
    12     int i, j, k = 0;
    13     A[1] = 1;
    14     for( i = 2; i <= sqrt(inf); i++)
    15        for ( j = 2 * i; j <= inf; j += i)
    16            A[j] = 1;
    17     for( i = 1; i <= inf; i++)
    18         if(!A[i])
    19             dp[k++] = i;
    20     return k;
    21 }
    22 
    23 int main( )
    24 {    
    25      int N, i, j, k, cnt;
    26      
    27      k = prime( );
    28      while(scanf("%d", &N) != EOF) {
          
    29         if(N == 0)
    30             continue;
    31          cnt = 0;
    32          
    33         for(i = 0; i < k; i++) {
          
    34             while((N%dp[i]) == 0) {
          
    35                 if(cnt)
    36                   printf("*");
    37                 printf("%d",dp[i]);
    38                 cnt++;
    39                 N = N / dp[i];
    40                 if (N == 1)
    41                     break;
    42             }
    43         }
    44         puts("");
    45     }
    46     return 0;
    47 }
    48

转载于:https://www.cnblogs.com/tangcong/archive/2011/07/20/2111322.html