Program: Prime Number Generator

Problem Statement

In this challenge, your task is to create a C program that will find all prime numbers from 3 to 100. The program should output each prime number separated by a space on a single line. You are required to create an array to store each prime number as it is generated. The first two prime numbers (2 and 3) can be hard-coded into the primes array. Utilize loops to find prime numbers and another loop to print out the primes array.

Hints

The criteria to identify a prime number is that it is not evenly divisible by any other previous prime numbers.
You can use the following as an exit condition in the innermost loop: p / primes[i] >= primes[i]. This is a test to ensure that the value of p does not exceed the square root of primes[i].
Your program can be more efficient by skipping any checks for even numbers (as they cannot be prime).

Feel free to attempt the challenge. When you're ready for guidance or if you have questions, let me know!

Algorithm

Initialize an array primes with the first two prime numbers: 2 and 3.
Initialize a counter count to 2 (representing the number of primes found).
Loop through odd numbers from 5 to 100.
For each odd number num: a. Assume it is prime (isPrime = 1). b. Check divisibility by previous prime numbers up to the square root of num. c. If divisible by any previous prime, set isPrime to 0 and break. d. If isPrime is still 1, add num to the primes array and increment count.
Print the prime numbers stored in the primes array.

Pseudocode

Initialize primes array with [2, 3]
Initialize count to 2

For num = 5 to 100, incrementing by 2:
    isPrime = 1

    For i = 0 to count - 1:
        If num % primes[i] == 0:
            Set isPrime to 0
            Break

    If isPrime == 1:
        Add num to primes array
        Increment count

Print prime numbers stored in the primes array

C Program

#include <stdio.h>

int main() {
    // Declare and initialize the primes array with the first two prime numbers
    int primes[50] = {2, 3};
    int count = 2; // Number of primes found, starting with the first two primes

    // Loop through odd numbers from 5 to 100 to find primes
    for (int num = 5; num <= 100; num += 2) {
        int isPrime = 1; // Assume the current number is prime

        // Check divisibility by previous primes
        for (int i = 0; i < count && primes[i] * primes[i] <= num; i++) {
            if (num % primes[i] == 0) {
                isPrime = 0; // Not prime if divisible by any previous prime
                break;
            }
        }

        // If the current number is prime, add it to the primes array
        if (isPrime) {
            primes[count++] = num;
        }
    }

    // Print the prime numbers separated by a space
    printf("Prime numbers from 3 to 100: ");
    for (int i = 0; i < count; i++) {
        printf("%d ", primes[i]);
    }

    return 0;
}

Explanation

The program initializes an array primes with the first two prime numbers (2 and 3) and a counter count to keep track of the number of primes found. It then loops through odd numbers from 5 to 100, checking each number's divisibility by previous prime numbers. If a number is prime, it is added to the primes array, and the counter is incremented. Finally, the program prints the prime numbers stored in the primes array.

This algorithm efficiently finds prime numbers within the specified range by utilizing the properties of prime numbers and optimizing the checking process.

Feel free to run the program and observe the output. If you have any questions or if there's anything you'd like to discuss, feel free to ask!

Last modified: 25 February 2024