fork(3) download
copy 
  1. #include<stdio.h>
  2. #include<math.h>
  3. int gcd(int a, int b)
  4. {
  5.     if(b==0) return a ;
  6.     else
  7.     return(gcd(b,a%b)) ;
  8. }
  9.  
  10. long long int mod(long long int a , long long int b , long long int n )
  11. {    
  12.      long long int x=1 , y=a ;
  13.      while(b>0)
  14.      {
  15.         if(b%2==1)  x = ((x%n)*(y%n))%n ;
  16.         y = ((y%n)*(y%n))%n ;
  17.          b/=2 ;
  18.      }
  19.      return x%n ;
  20. }
  21.  
  22. int isprimes(long long int u)
  23. {  
  24.     if(u==3)
  25.     return 1 ;
  26.      int a = 2 , i ;
  27.      long long int k , t = 0 , r , p ;
  28.      k = u-1 ;
  29.      while(k%2==0)
  30.      { k/=2 ; t++ ; }
  31.  
  32.          while(a<=3)                                                              /*der are no strong pseudoprimes common in base 2 and base 3*/
  33.          {   
  34.          r = mod(a,k,u) ;
  35.              for(i = 1 ; i<=t ; i++)
  36.              {
  37.                   p = ((r%u)*(r%u))%u ;
  38.                   if((p==1)&&(r!=1)&&(r!=(u-1)))
  39.                   {  return 0 ; }
  40.                   r = p ;
  41.              }
  42.           if(p!=1)
  43.           return 0 ;
  44.          else
  45.           a++ ;
  46.          } 
  47.  
  48.           if(a==4)
  49.           return 1 ;
  50.  
  51. }
  52.  
  53. long long int pol(long long int u)
  54. { 
  55.   long long int x = 2 , k , i , a , y , c , s;
  56.   int d = 1 ;
  57.    k = 2 ;
  58.    i = 1 ;
  59.    y = x ;
  60.    a = u ;
  61.    if(isprimes(u)==1)
  62.    { 
  63.      return 1;
  64.    }
  65.    c=-1 ;
  66.    s = 2 ;
  67.    while(1)
  68.    {
  69.      i++;
  70.      x=((x%u)*(x%u)-1)% u ;
  71.  
  72.      d = gcd(abs(y-x),u) ;
  73.  
  74.      if(d!=1&&d!=u)
  75.      { printf("%d ",d);
  76.        while(a%d==0) { a=a/d;  }
  77.  
  78.         x = 2 ;
  79.         k = 2 ;
  80.         i = 1 ;
  81.         y = x ;
  82.         if(a==1)
  83.         { return 0 ; }
  84.         if(isprimes(a)!=0)
  85.         { return a ; }
  86.         u=a ;
  87.  
  88.      }
  89.      if(i==k)
  90.      {y = x ; k*=2 ; c = x ;}                                                       /*floyd cycle detection*/
  91.         if(c==x)                                                                 
  92.      { x = ++s ; }
  93.     }
  94.     return ;
  95.  
  96. }
  97.  
  98. int main()
  99. {
  100.    long long int t ;
  101.     long long int i , n , j , k , a , b  , u ;
  102.     while(scanf("%lld",&n)&&n!=0)
  103.     { u = n ; k = 0 ;
  104.     while(u%2==0)
  105.        {  u/=2 ; k = 1 ; }
  106.       if(k==1) printf("2 ") ;
  107.       if(u!=1)
  108.       t = pol(u) ;
  109.         if(u!=1) 
  110.       {
  111.            if(t==1)
  112.            { printf("%lld",u) ; }
  113.            else
  114.            if(t!=0)
  115.            { printf("%lld",t) ; }
  116.       }
  117.           printf("\n");
  118.     }
  119.     return 0;
  120. }
  121.  
  122.  
Success #stdin #stdout 0.01s 1728KB
comments (?)
stdin
copy 
10
561
1729
15481
999999999
0
stdout
copy 
2 5
3 17 11
7 13 19
137 113
3 37 333667
https://ideone.com/esBXz
language:
C (gcc 8.3)
created:
11 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!