All the primes up to n – Python Exercise with Solution

Print every prime number up to n, and how many there are.

What to build

One loop inside another, in which the inner loop stops early.

Requirements

Read n.
Print all the primes from 2 to n on one line, separated by single spaces.
Print count: K on the next line.

Input

One whole number n.

Output

Two lines.

Constraints

n is from 2 to 5000.

Example

Input:

Output:

2 3 5 7
count: 4

Why it works

If a number has a divisor larger than its square root, it must also have a smaller one, so the search can stop there. One divisor is proof enough, so break saves more work.

Examples

Example 1 · Input

Expected output

2 3 5 7
count: 4

Example 2 · Input

Expected output

2
count: 1

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Use an inner loop to look for a divisor of each candidate.

Hint 2

You can stop at the first divisor, with break.

Hint 3

You only need to try divisors d while d * d <= candidate.

Solution

Show one correct solution (try it yourself first)

n = int(input())
primes = ""
count = 0
for candidate in range(2, n + 1):
    is_prime = True
    d = 2
    while d * d <= candidate:
        if candidate % d == 0:
            is_prime = False
            break
        d += 1
    if is_prime:
        primes += str(candidate) + " "
        count += 1
print(primes.strip())
print("count:", count)

Lesson: Nested loops →