Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

为什么老wa 大家看看 欧拉函数的

Posted by xiaxia at 2006-02-28 11:48:35 on Problem 2407
#include <iostream>
using namespace std;

const int MAX = 31624 + 10; //1000000000的平方根
bool nprime[MAX];
int prime[MAX];
int main()
{
	memset(nprime, 0, sizeof(bool)*MAX);
	int i, j;
	for(i = 2; i < MAX/2; i ++)
	{
		for(j = i*i; j < MAX; j += i)
              nprime[j] = true;
	}
	int c = 0;
	for(i = 2; i < MAX; i ++)
		if(!nprime[i])
		{		
		    prime[c ++] = i;
		}
	int n;
	while(cin >> n && n)
	{
		int ans = n;
		for(i = 0; i < c; i ++)
		 {
			if(n%prime[i] == 0)
			{
				ans /= prime[i];
				ans *= prime[i] - 1;		
			}
		 }
		 if(ans == n)
			 ans = n - 1;
		 cout << ans << endl;
	}
	return 0; 
}    

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator