Week 1: Exercises

1. Multiples

Solve Project Euler's Problem 1 in C#:

Find the sum of all the multiples of 3 or 5 below 1000.

2. Fibonacci Sum

Solve Project Euler's Problem 2 in C#:

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

3. Prime Factor

Solve Project Euler's Problem 3 in C#:

What is the largest prime factor of the number 600851475143 ?

4. Largest Palindrome Product

Solve Project Euler's Problem 4 in C#:

Find the largest palindrome made from the product of two-digit numbers.

5. 10001st Prime

Solve Project Euler's Problem 7 in C#:

What is the 10001st prime number?

6. Prime Counting

In number theory, the prime-counting function π(x) denotes the number of prime numbers that are less than or equal to x. (It is unrelated to the number π.)

a) Write a C# program that computes and prints π(1,000,000). Use trial division for primality testing.

b) Write the same program in Python.

c) Compare the running time of the two programs.

7. Last Digits

Write a program that computes and prints the last 5 digits of the integer 2¹⁰⁰⁰.

8. Primality Claim

Consider this claim:

For every integer n ≥ 2, n is prime if and only if 2ⁿ – 2 is divisible by n.

For example:

• n = 2: 2² – 2 = 4 – 2 = 2 is divisible by 2

• n = 3: 2³ – 2 = 8 – 2 = 6 is divisible by 3

• n = 4: 2⁴ – 2 = 16 – 2 = 14 is not divisible by 4

• n = 5: 2⁵ – 2 = 32 – 2 = 30 is divisible by 5

We see that the claim is true at least through n = 5.

Write a C# program that determines whether the claim is true for all values through n = 1000. If the claim fails for any such n, print its value.