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

最后如果有一个很大的素数,超过sqrt(10^9)的你没考虑到

Posted by flymouse at 2007-07-24 18:25:17 on Problem 2407
In Reply To:为什么老wa 大家看看 欧拉函数的 Posted by:xiaxia at 2006-02-28 11:48:35
> #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