CODEWITHSUNDEEP
c
Ikhtiar Mahmud
Ikhtiar Mahmud

Reputation: 77

Find prime number with minimum number of loop

I have written this code for finding prime numbers from 1 to 100. I have used two-loop to solve this problem.

But, Is it possible to find the prime number from 1 to 100 with only one loop?

Is there any formula?

#include <stdio.h>
 
int main(void)
{
    int i, number = 1, count; 
  
    printf("Prime Numbers from 1 to 100 are: \n"); 
    while (number <= 100) {
        count = 0;
        i = 2;
        while (i <= number/2) {
            if (number%i == 0) {
                count++;
                break;
            }
            i++;
        }   
        if (count == 0 && number != 1 ) {
            printf("%d ", number);
        }
        number++; 
    }
    return 0;
}

Upvotes: 0

Views: 570

Answers (1)

Antonin GAVREL
Antonin GAVREL

Reputation: 11249

You can use the following function:

#include <stdio.h>
#include <string.h>

#define bool    unsigned char
#define true    1
#define false   0
// https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
void printPrimes(int n) {
    if (n < 0 ) // handle misused of function
        return ;
    bool isPrime[n + 1];
    memset(isPrime, true, n + 1);
    int cnt = 0; // NB: I use the counter only for the commas and final .\n, its optional.

    if (n >= 2) { // only one even number can be prime: 2
        ++cnt;
        printf("2");
    }
    for (int i = 3; i <= n ; i+=2) { // after what only odd numbers can be prime numbers
        if (isPrime[i]) {
            if (cnt++)
                printf(", ");
            printf("%d", i); // NB: it is better to print all at once if you can improve it
        }
        for (int j = i * i; j <= n; j+=i*2) // Eratosthenes' Algo, sieve all multiples of current prime, skipping even numbers.
            isPrime[j] = false;
    }
    printf(".\n");
}

int main(void) {
    printPrimes(100);
    return 0;
}

output:

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.

Thanks to the sieves of Eratosthenes you can reduce the amount of iteration you are doing in your secondary loop.

NB: if your user input is high (bigger than squareroot of INT_MAX) you should replace j = i * i by j = i * 3 to avoid overflow

NB2: If you don't care about the formatting you can remove the commas and dot, as well as the cnt variable.

NB3: You can iterate 2 per 2 as only 2 is a prime number, it speeds up substantially your program

Upvotes: 1

Related Questions