Prime Number Program in C with Code

This tutorial is designed for both beginners and intermediate programmers who are eager to gain practical experience in C programming, particularly those preparing for competitive programming or university exams.

If you're serious about advancing your programming career, consider enrolling in Uncodemy's industry-focused C Programming Course in Noida for hands-on knowledge and real-time project experience.

What is a Prime Number?

A prime number is a natural number greater than one that can only be divided by one and itself. In simpler terms, it's a number that has exactly two distinct positive divisors: one and the number itself.

Examples of Prime Numbers:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29

Characteristics of Prime Numbers:

-        A prime number is always greater than one.

-        It has only two divisors.

-        Two is the only even prime number.

-        One is not classified as a prime number.

How to Check if a Number is Prime:

The logic for checking if a number is prime is quite simple. A number is considered prime if it isn't divisible by any other number except for one and itself.

Optimized Approach:

Instead of checking all the way up to the number minus one, we can streamline the process by only checking divisibility up to the square root of the number. This adjustment reduces the time complexity from O(n) to O(√n), making the program significantly more efficient.

Prime Number Program in C to Check a Single Number

Let's dive into creating a C program that checks if a given number is prime.

Program Breakdown:

-        First, we’ll ask the user to input a number.

-        Next, we need to see if that number is less than or equal to one. If it is, we can confidently say it’s not a prime number.

-        Then, we’ll set up a loop that runs from two up to half of the number.

-        If we find that the number can be divided evenly by any of the numbers in our loop, it’s not prime.

-        If it passes all those checks, then we can declare it a prime number!

C Program

#include <stdio.h>

int main() {

int num, i, isPrime = 1;

    printf("Enter a number: ");

    scanf("%d", &num);

if (num <= 1) {

        printf("%d is not a prime number", num);

     return 0;

}

for (i = 2; i <= num / 2; i++) {

     if (num % i == 0) {

            isPrime = 0;

            break;

     }

}

if (isPrime)

        printf("%d is a prime number", num);

else

        printf("%d is not a prime number", num);

return 0;

}

Sample Output

Enter a number: 13

13 is a prime number

Enter a number: 20

20 is not a prime number

C Program to Print Prime Numbers from One to Hundred

In this program, we print all prime numbers between one and hundred using a loop and condition-based logic.

C Program

#include <stdio.h>

int main() {

int i, j, isPrime;

    printf("Prime numbers between 1 and 100 are:\n");

for (i = 2; i <= 100; i++) {

     isPrime = 1;

     for (j = 2; j <= i / 2; j++) {

         if (i % j == 0) {

                isPrime = 0;

                break;

         }

     }

     if (isPrime)

            printf("%d ", i);

}

return 0;

}

Output:

Prime numbers between 1 and 100 are:

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

C Program to Find Prime Numbers Between Two Intervals

This is a variation where the user inputs the start and end values of a range and the program prints all prime numbers in that range.

C Program

#include <stdio.h>

int main() {

int start, end, i, j, isPrime;

    printf("Enter the start number: ");

    scanf("%d", &start);

    printf("Enter the end number: ");

    scanf("%d", &end);

    printf("Prime numbers between %d and %d are:\n", start, end);

for (i = start; i <= end; i++) {

     if (i < 2)

            continue;

     isPrime = 1;

     for (j = 2; j <= i / 2; j++) {

         if (i % j == 0) {

                isPrime = 0;

                break;

         }

     }

     if (isPrime)

            printf("%d ", i);

}

return 0;

}

Sample Output

Enter the start number: 10

Enter the end number: 30

Prime numbers between 10 and 30 are:

11 13 17 19 23 29

Time Complexity of Prime Number Programs

When it comes to checking if a number is prime using the basic method, the time complexity is O(n), where n represents the number itself. But if we apply the square root optimization, it improves to O(√n). If you're looking to print multiple prime numbers within a certain range, the overall complexity shifts to O(n * √n).

Space Complexity

All the programs we've talked about so far utilize constant space, which is O(1), since we're not allocating any extra memory that scales with the input size.

Real-Life Applications of Prime Numbers

Prime numbers aren't just an abstract idea; they have significant real-world applications, including:

-        Cryptography and network security

-        Hashing algorithms

-        Random number generation

-        Data encryption and compression

Best Practices for Writing Prime Number Programs

-        Always consider edge cases like 0 and 1

-        Use square root logic to optimize for larger inputs

-        Steer clear of unnecessary nested loops

-        Add comments to your code for improved readability

Why Learn Prime Number Logic in C

Understanding how to write a prime number program can help you grasp:

-        The mechanics of loops

-        How conditional statements function

-        Efficient variable usage

-        Code optimization

If you're just starting out in programming, getting a handle on this type of logic will significantly enhance your problem-solving skills.

For hands-on coding experience, doubt-clearing sessions, and live projects, think about enrolling in the expert-led C Programming Course in Noida offered by Uncodemy. It will provide you with a strong foundation in both basic and advanced C concepts.

Conclusion

Creating a prime number program in C is a great way to sharpen your logical thinking and get a solid grip on programming fundamentals. In this blog, we took a deep dive into various C programs that check if a number is prime, print a series of prime numbers, and manage inputs dynamically.

Grasping and applying these concepts is crucial for anyone eager to advance as a programmer. Keep experimenting with different variations of this program, fine-tune your code, and strive to improve each day.

And if you're looking to elevate your C programming skills even further, don’t miss out on the C Programming Course in Noida offered by Uncodemy, where industry experts will walk you through real-world coding challenges.

Frequently Asked Questions of Prime number in C

1. What is the smallest prime number?

The smallest prime number is two.

2. Why is one not a prime number?

One isn’t considered a prime number because it has only one positive divisor. A prime number must have exactly two positive divisors.

3. Is zero a prime number?

No, zero is not a prime number. It can be divided by every number.

4. What is the only even prime number?

Two is the only even prime number since all other even numbers can be divided by two and at least one other number.

5. What is the time complexity of checking a prime number?

The time complexity of a basic approach is O(n). However, with the square root optimization, it becomes O(√n).

6. Can we use arrays to store prime numbers?

Absolutely! Arrays can be used to keep a list of prime numbers, especially when you want to print all primes within a certain range.

7. How is this program useful in competitive programming?

Understanding prime number logic is often key in number theory problems. Efficient prime checking can help you solve challenges more quickly in competitions.

8. How can I improve this program further?

You might consider using the Sieve of Eratosthenes algorithm for better performance when generating prime numbers over a large range.