C program to find sum of all prime numbers from 1 to n

Prime numbers are fundamental in number theory due to their properties and role in various algorithms. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. This article will discuss a C program to find the sum of all prime numbers from 1 to a given number n.

Steps to Approach the Problem

To find the sum of all prime numbers from 1 to n, we need to follow these steps:

1. Input the number n: The user will provide the upper limit to which the sum of prime numbers will be calculated.
2. Check for Prime Numbers: For each number in the range from 2 to n, check if the number is prime.
3. Sum the Prime Numbers: If the number is prime, add it to the sum.
4. Output the Sum: After iterating through all numbers, output the calculated sum.

Explanation

1. Input the Number n

We will prompt the user to enter the value of n and store it in a variable.

2. Check for Prime Numbers

To check if a number num is prime, we need to ensure it has no divisors other than 1 and itself. We can optimize this by only checking for divisors up to the square root of num. If a number has no divisors up to its square root, it has no other divisors.

3. Sum the Prime Numbers

Initialize a sum variable to 0. For each number from 2 to n, check if it is prime. If it is, add it to the sum.

4. Output the Sum

Finally, print the sum of all prime numbers found in the given range.

Write a C program to find sum of all prime numbers from 1 to n

Here's the C program that implements the above logic:

#include <stdio.h>
#include <math.h>

// Function to check if a number is prime
int isPrime(int num) {
    if (num <= 1) return 0;
    if (num <= 3) return 1;
    if (num % 2 == 0 || num % 3 == 0) return 0;

    for (int i = 5; i * i <= num; i += 6) {
        if (num % i == 0 || num % (i + 2) == 0) return 0;
    }
    return 1;
}

int main() {
    int n;
    long long sum = 0;

    // Input the upper limit
    printf("Enter the value of n: ");
    scanf("%d", &n);

    // Calculate the sum of prime numbers
    for (int i = 2; i <= n; i++) {
        if (isPrime(i)) {
            sum += i;
        }
    }

    // Output the result
    printf("The sum of all prime numbers from 1 to %d is: %lld", n, sum);

    return 0;
}

Output

Enter the value of n: 10
The sum of all prime numbers from 1 to 10 is: 17

Explanation of the Code

1. Prime Check Function (isPrime):
   • This function checks if a number is prime.
   • For numbers less than or equal to 1, it returns 0 (not prime).
   • For numbers 2 and 3, it returns 1 (prime).
   • For numbers divisible by 2 or 3, it returns 0.
   • For numbers greater than 3, it checks divisors from 5 to the square root of the number, incrementing by 6 in each iteration (as primes are of the form 6k ± 1).
2. Main Function:
   • Prompts the user to input the upper limit n.
   • Iterates through all numbers from 2 to n and checks if they are prime.
   • Sums the prime numbers and prints the final result.