proot.cpp

求原跟的VC程序,可计算2-10000之间的质数的原跟

#include"math.h"
#include"iostream.h"
bool isprimenumber(long n)
{
	bool flag=true;
	if(n<1)
		flag=false;
	for(int i=2;i<=sqrt(n);i++)
	{
		if(fmod(n,i)==0)
		{			
			flag=false;
			break;
		}
	}
	return flag;
}
void main()
{
	long n,j,l,a,next,count=0,remaining;
	long* proot;
	cout<<"input a prime number please:"<<endl;
	cin>>n;
	while(!isprimenumber(n))
	{
		cout<<"Ensure you input a prime number between 2 and 10000 please:"<<endl;
	cin>>n;
	}
	proot=new long[n];
	if(n==2)
	{
		proot[0]=1;
		count=1;		
	}

	for(a=2;a<n;a++)
	{
		next=a;
		for(l=1;l<n;l++)
		{	
			remaining=next%n;			
			next=remaining*a;	
			if(remaining==1)
				break;
		}
		if(l==n-1)
		{
			proot[count]=a;
			count++;		
		}		
	}
	if(count==0)		
		cout<<n<<"没有原根"<<endl;	
	else
	{
		cout<<n<<"共有"<<count<<"个原根："<<endl;
		for(j=0;j<count;j++)
			cout<<proot[j]<<endl;
			
	}
	delete []proot;

}