fork download
  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
stdin
10
561
1729
15481
999999999
0
stdout
2 5
3 17 11
7 13 19
137 113
3 37 333667