## SPOJ 8456. PRIMITIVEROOTS

SPOJ 8456. PRIMITIVEROOTS is related to number theory. Product of primitive roots of p ( prime number ) mod p is equal to 1.The product of all primitive roots of prime p 3 is ( mod p ). History of the theory of numbers By Leonard Eugene Dickson on page 183.This problem is not allowed in Haskell. Accepted C++ code.

#include<cstdio> #include<iostream> #include<cmath> using namespace std; bool p[10010]; void prime() { for(int i=2 ; i*i <=10000 ; i++ ) if(!p[i]) for(int j = i*i ; j <=10000 ; j += i ) p[j]=1; //for(int i=2; i <= 20 ; i++) if(!p[i]) cout<<i<<" ";cout<<endl; } int main() { prime(); int n , t , x=1 ; for( scanf("%d",&t) ; t>0 ; t--) { scanf("%d",&n); if( n == 3 ) printf("%d:2\n", x++); else if ( !p[n] ) printf("%d:1\n",x++); else printf("%d:NOTPRIME\n",x++); /*if( t != 1 ) printf("\n");*/ } }

Advertisements

No comments yet.

## Leave a Reply