language: C (gcc-4.7.2)
date: 382 days 9 hours ago
link:
visibility: private 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122

#include<stdio.h>
#include<math.h>
int gcd(int a, int b)
{
    if(b==0) return a ;
    else
    return(gcd(b,a%b)) ;
}
 
long long int mod(long long int a , long long int b , long long int n )
{    
     long long int x=1 , y=a ;
     while(b>0)
     {
        if(b%2==1)  x = ((x%n)*(y%n))%n ;
        y = ((y%n)*(y%n))%n ;
         b/=2 ;
     }
     return x%n ;
}
 
int isprimes(long long int u)
{  
    if(u==3)
    return 1 ;
     int a = 2 , i ;
     long long int k , t = 0 , r , p ;
     k = u-1 ;
     while(k%2==0)
     { k/=2 ; t++ ; }
   
         while(a<=3)                                                              /*der are no strong pseudoprimes common in base 2 and base 3*/
         {   
         r = mod(a,k,u) ;
             for(i = 1 ; i<=t ; i++)
             {
                  p = ((r%u)*(r%u))%u ;
                  if((p==1)&&(r!=1)&&(r!=(u-1)))
                  {  return 0 ; }
                  r = p ;
             }
          if(p!=1)
          return 0 ;
         else
          a++ ;
         } 
         
          if(a==4)
          return 1 ;
      
}
       
long long int pol(long long int u)
{ 
  long long int x = 2 , k , i , a , y , c , s;
  int d = 1 ;
   k = 2 ;
   i = 1 ;
   y = x ;
   a = u ;
   if(isprimes(u)==1)
   { 
     return 1;
   }
   c=-1 ;
   s = 2 ;
   while(1)
   {
     i++;
     x=((x%u)*(x%u)-1)% u ;
 
     d = gcd(abs(y-x),u) ;
    
     if(d!=1&&d!=u)
     { printf("%d ",d);
       while(a%d==0) { a=a/d;  }
       
        x = 2 ;
        k = 2 ;
        i = 1 ;
        y = x ;
        if(a==1)
        { return 0 ; }
        if(isprimes(a)!=0)
        { return a ; }
        u=a ;
       
     }
     if(i==k)
     {y = x ; k*=2 ; c = x ;}                                                       /*floyd cycle detection*/
        if(c==x)                                                                 
     { x = ++s ; }
    }
    return ;
    
}
 
int main()
{
   long long int t ;
    long long int i , n , j , k , a , b  , u ;
    while(scanf("%lld",&n)&&n!=0)
    { u = n ; k = 0 ;
    while(u%2==0)
       {  u/=2 ; k = 1 ; }
      if(k==1) printf("2 ") ;
      if(u!=1)
      t = pol(u) ;
        if(u!=1) 
      {
           if(t==1)
           { printf("%lld",u) ; }
           else
           if(t!=0)
           { printf("%lld",t) ; }
      }
          printf("\n");
    }
    return 0;
}