Write a program that takes an integer from standard input and prints all prime n

Question

Write a program that takes an integer from standard input and prints all prime numbers that are smaller than it to standard output. Recall that a prime number is a natural number greater than 1 whose only positive divisors are 1 and itself. At the start of the program, prompt the user to input a number by printing "Input a number greater than 2: ". If the user's input is less than or equal to 2, then print "No prime number is smaller than . ", where is replaced by the number input by the user. If the user inputs a number greater than 2, then print "Prime numbers smaller than : ". Then, on the same line, print out a list of all prime numbers that are smaller than the input. In your list, each prime number must be separated by one space and a newline must be printed immediately after the last number in the list. As part of your program, you must make a function that takes an integer as an argument, returns 1 if the integer is prime, and returns 0 otherwise. You can use the following function prototype: int isPrime(int number); Example input/output pairs (excluding the prompt) are provided below: Input: 6; Output: Prime numbers smaller than 6: 2 3 5 Input: 23; Output: Prime numbers smaller than 23: 2 3 5 7 11 13 17 19 Input: 1; Output: No prime number is smaller than 1.

Explanation / Answer

Hi buddy, I've written 2 programs for you. The first one is the one you asked for and the second one uses sieve method. That is much faster .

Method 1 :

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

int isPrime(int n){
    //Finding square root of n
    int e = (int)sqrt((float)n);
    //if n is even, return false
    if(n%2==0){
        return 0;
    }
    //Check whether n is divisible by all the odd numbers till e
    for(int i=3;i<=e;i+=2){
        if(n%i==0){
            return 0;
        }
    }
    return 1;
}

int main(void) {
        //Prompting and reading an integer
       printf("Input a number greater than 2 ");
       int n;
       scanf("%d",&n);
      
       //If number less than 2, give msg
       if(n<=2){
            printf("No prime number is smaller than %d ",n);
            return 0;
       }
      
       printf("Input : %d ; Output : 2 ",n);
      
       for(int i=3;i<=n;i++){
            if(isPrime(i)==1){
                printf("%d ",i);
            }
       }
       printf(" ");
       return 0;
}

Input : 20

OUTPUT :

Input a number greater than 2
Input : 20 ; Output : 2 3 5 7 11 13 17 19

Method 2 :

#include <stdio.h>

int main(void) {
        //Prompting and reading an integer
       printf("Input a number greater than 2 ");
       int n;
       scanf("%d",&n);
      
       //If number less than 2, give msg
       if(n<=2){
            printf("No prime number is smaller than %d ",n);
            return;
       }
      
       printf("Input : %d ; Output : 2 ",n);
      
       //Initialize an array of n intergers and initialize with 1
       int primes[n+1];
       for(int i=0;i<=n;i++){
            primes[i] = 1;
       }
      
       //I'm using sieve method to fill populate the array
       for(int i=2;i<=n;i++){
            for(int j=2;j*i<=n;j++){
                //Number i*j can't be prime number because both i and j are factors
                primes[i*j] = 0;
            }
       }
      
       //Print the numbers whose prime[i] is 1. (You can skip even numbers (+=2))
       for(int i=3;i<=n;i+=2){
            if(primes[i]==1){
                printf("%d ",i);
            }
       }
       printf(" ");
       return 0;
}

Input : 20

OUTPUT :

Input a number greater than 2
Input : 20 ; Output : 2 3 5 7 11 13 17 19

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.