Generate the first n prime numbers

LAB B04 · 01

Understand the task.

Aim: Generate the first n prime numbers.

Review the related theory in Unit 4.

LAB B04 · 02

Know what goes in and what comes out.

One count n from 1 to 100. Generate the first n primes, rather than all primes less than or equal to n.

5

First 5 primes: 2 3 5 7 11

Source programs read the documented input directly, without prompt text, so the same sample works in the embedded compiler’s STDIN field.

LAB B04 · 03

Plan the steps before writing code.

1. Read and validate the requested count. Start candidate at 2 and count at zero.
2. Use isPrime to test the candidate.
3. If prime, print it and increment count.
4. Advance candidate and repeat until count equals n.
5. Finish the output line.

LAB B04 · 04

One complete program. Ready to run.

#include <stdio.h>
int isPrime(int number);
int main(void)
{
    int n, count = 0, candidate = 2;
    if (scanf("%d", &n) != 1 || n < 1 || n > 100) {
        puts("Enter a prime count from 1 to 100."); return 1;
    }
    printf("First %d primes:", n);
    while (count < n) {
        if (isPrime(candidate)) { printf(" %d", candidate); count++; }
        candidate++;
    }
    putchar('\n');
    return 0;
}
int isPrime(int number)
{
    int divisor;
    if (number < 2) return 0;
    for (divisor = 2; divisor <= number / divisor; divisor++) {
        if (number % divisor == 0) return 0;
    }
    return 1;
}

gcc B04-first-n-primes.c -o program

LAB B04 · 05

Connect each statement to its purpose.

• 1 is not prime, so the search starts at 2.
• isPrime checks possible divisors only while divisor <= number / divisor, equivalent to divisor² <= number for positive values.
• The division form avoids overflowing a divisor * divisor expression for larger extensions of the program.
• The smallest divisor found proves the candidate composite; otherwise the function returns 1.
• The loop terminates after n successful prime tests, not after checking n candidates.

LAB B04 · 06

Follow the sample calculation.

LAB B04 · 07

Check more than one input.

Time and storage

If p_n is the nth prime, the straightforward trial-division search uses at most O(p_n × sqrt(p_n)) time and O(1) extra working space.

Start with the sample, then test a boundary and a case that changes the result. A correct sample alone does not establish that every input is handled correctly.

LAB B04 · 08

Use the real C compiler.

Choose an example and load it into the embedded C compiler. Select I/O inside the compiler, check the sample STDIN, and press Run. Change the input or edit the source to explore a different case.

5

First 5 primes: 2 3 5 7 11

#include <stdio.h>
int isPrime(int number);
int main(void)
{
    int n, count = 0, candidate = 2;
    if (scanf("%d", &n) != 1 || n < 1 || n > 100) {
        puts("Enter a prime count from 1 to 100."); return 1;
    }
    printf("First %d primes:", n);
    while (count < n) {
        if (isPrime(candidate)) { printf(" %d", candidate); count++; }
        candidate++;
    }
    putchar('\n');
    return 0;
}
int isPrime(int number)
{
    int divisor;
    if (number < 2) return 0;
    for (divisor = 2; divisor <= number / divisor; divisor++) {
        if (number % divisor == 0) return 0;
    }
    return 1;
}

LAB B04 · 09

Explain why the program works.

LAB B04 · 10

Build the next skill.

Read the viva answers, try the extra cases, and return to the lab index to mark this exercise as practised.