My Weblog

Blog about programming and math

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 \not= 3 is \equiv 1  ( 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

July 17, 2011 - Posted by | Programming | , , ,

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: