1787.cpp

来自「杭电 acm部分代码 有兴趣的可以下载 谢谢」· C++ 代码 · 共 59 行

#include <iostream>
#include <cmath>
using namespace std;
int n, num, mm;
bool prime;
int main()
{
	int i;
	while (cin >> n, n)
	{
		double t = sqrt(double(n)); 
		prime = true;
		if (n == 2 || n == 3)
		{
			prime = true;
		}
		else
		{
			for (i = 2; i <= t; i++)
			{
				if (n % i == 0)
				{
					prime = false;
					break;
				}
			}
		}
		if (prime == true)
		{
			cout << 0 << endl;
		}
		else
		{
			num = n;
			mm  = n;
			while (n != 1)
			{
				if (n % i == 0)
				{				
					while (n % i == 0)
					{
						n /= i;	
					}
					num = (num / i) * (i - 1);
				}
				if (i == 2)
				{
					i += 1;
				}
				else
				{
					i += 2;
				}
			}
			cout << mm - 1 - num << endl;
		}
	}
	return 0;
}