import sys #import the sys module to access command line arguments

#The function below creates a list of all primes less than n

def createPrimeNumberArray$($n$)$:

primes $=[]$ #create an empty list to store the prime numbers

isPrime $=[$True$]*$ n #create a list of n elements, all set to True

for i in range$(2,$ n$)$: #iterate through the list of numbers from $2$ to n

if isPrime$[$i$]$: #check if i is prime

primes.append$($i$)$ #add the prime number to the list

#starting with i$^2,$ mark all multiples of i as False

#$($this is a shortcut to help avoid checking redundant multiples$)$

for j in range$($i $*$ i$,$ n$,$ i$)$:

isPrime$[$j$]=$ False

return primes

def totient$($n$,$ primes$)$:

#below calculates the result of the product of $(1-1/$p$)$ for each prime p that divides n

result $=1$

if n in primes:

return n$-1$

for prime in primes:

if prime $>$ n:

break

if n $\%$ prime $==0$: # determine if prime evenly divides n

result $=$ result $*(1-1/$ prime$)$

#At this point, the variable result is the product of $(1-1/$p$)$ for each prime p that divides n

return result; #$<---------------$THE ERROR IS RIGHT HERE!!! MAKE ONE SMALL CHANGE TO FIX THE ERROR.

#ONCE YOU FIX IT HERE ARE MORE HINTS TO FINISH THE PROGRAM

#The totient function is supposed to return an integer value, not a floating point $($decimal$)$ value.

#You can use the int$()$ function to convert the result to an integer before returning it$.$

#make sure the number of command line arguments is correct

numCommandArgs $=$ len$($sys$.$argv$)$

if numCommandArgs $!=2$: # the program name and the two arguments

print$("$You must provide an integer $($n$)$ to be evaluated $->$ Usage: python sieve$\_$totient.py n$")$

sys$.$exit$()$

#make sure the command line argument is an integer greater than $2$

n $=$ int$($sys$.$argv$[1])$ #get the integer from the command line

if n $<2$: #make sure the integer is greater than $2$

print$("$The integer must be greater than $2")$

sys$.$exit$()$

#call the functions to create the prime number array and calculate the totient value

primeArray $=$ createPrimeNumberArray$($n$+1)$ #create the prime number array $($one was added in case n is a prime number$)$

totientValue $=$ totient$($n$,$ primeArray$)$ #calculate the totient value

print$("$There are $\{0!$s$\}$ prime numbers less than or equal to $\{1!$s$\}".$format$($len$($primeArray$),$n$))$ #print the number of primes less than n

print$("$The totient function of $\{0!$s$\}$ is $\{1!$s$\}".$format$($n$,$totientValue$))$ #print the totient value of n

# Sieve of Eratosthenes and Euler's Totient Function

This assignment will demonstrate how to implement the Sieve of Eratosthenes and Euler's Totient Function from a very easy sequential Python$3$ implementation.

# Product Owner Statement

As a person very interested in mathematics and the Python programming language I decided to create a simple program that will calculate the totient function for a given value. I believe I am close to completing my simple project but my code has an error in it$.$ I need your help and knowledge of the General Totient Function Formula to finish my project.

My code runs when I use the command line argument below:

$```$

python sieve$\_$totient.py $600$

$```$

I know my program should give the following:

$```$

There are $109$ prime numbers less than $600$

The totient function of $600$ is $160$

$```$

Unfortunately it prints out the following:

$```$

There are $109$ prime numbers less than $600$

The totient function of $600$ is $0\mathrm{.}2666666666666667$

$```$

# Acceptance Criteria

The following must be implemented to receive credit for this assignment.

$-$ The code provided does not need to be altered significantly to complete the assignment. Before you start making changes make sure you read the code comments. There may be hints on how to fix the program.

$-$ The final output for a totient value should be an integer and correct.

# Have Fun With it

Once you complete the assignment take a moment to recoginize the code is not optimized at all. Yet it is still able to calculate a the totient value for very large values $($and the required prime list to do it$).$ Try calculating the totient function for $100,$ then one million, and finally ten million. Notice the time differences. Remember Python is very slow. Just imagine implementing this with faster languages using optimizations.