The Phi function (sample, not for credit)

The quantity φ(n) is defined to be the number of integers between 1 and n (inclusive) that are relatively prime to n. Your task is to compute this quantity for various values of n.


The first line gives the number of test cases, T. T test cases follow. Each test case is a single line containing one positive integer, n.


For each test case, output one line containg "Case #x: y", where x is the case number (starting from 1) and y is the value φ(n).


1 ≤ T ≤ 100.
Small dataset: 1 ≤ n ≤ 1 000 000.
Large dataset: 1 ≤ n ≤ 1018.


Input Output
Case #1: 6
Case #2: 20
Case #3: 72
Case #4: 96
Case #5: 4000

Input and output files

Small: Input / Output
Large: Input / Output

Sample solutions

Below are links to four different solutions to this problem. These show two different algorithms: a naive implementation which explicitly checks every number from 1 to n to see if it is coprime (using the Euclidean algorithm), and an implementation which removes prime factors one by one and uses the multiplicative property of the phi function. Each algorithm is implemented in C++ and in Python.

The naive algorithm is fast enough to complete the small input in a couple minutes, but would be hopeless for the large input. The faster algorithm can complete the large input in about ten minutes. There are various optimizations that could make it faster still, which I encourage you to search for.

Naive algorithmFast algorithm
(can do small input) (can do large input)
C++ phi_naive.cpp phi.cpp