Hello, OnlineGDB Q&A section lets you put your programming query to fellow community users. Asking a solution for whole assignment is strictly not allowed. You may ask for help where you are stuck. Try to add as much information as possible so that fellow users can know about your problem statement easily.

C program to display prime numbers between 1 to n

+7 votes
asked May 17, 2021 by Anitha (430 points)
With the use of functions

5 Answers

0 votes
answered May 18, 2021 by Peter Minarik (84,720 points)
edited May 18, 2021 by Peter Minarik
 
Best answer

Try to Do the Code First

This looks like a school assignment for me.

Your best interest is to give it a try and if you get stuck, post what you did and we can help you fix it. But if we just give you the answer straight away, you'll learn nothing. :(

Pointers

Here are some pointers that may help you

What is a Prime Number

A prime number as defined in Wikipedia:

A natural number (1, 2, 3, 4, 5, 6, etc.) is called a prime number (or a prime) if it is greater than 1 and cannot be written as the product of two smaller natural numbers.

So 5 is a prime as it cannot be written as a product of two smaller natural numbers. However, 6 is not a prime (it's a composite number) as it can be written as a product of two smaller natural number: 6 = 2 * 3.

You can find various computational methods, i.e. how to find prime numbers. I'd advise trying to implement either (or both) of the first two: "division method" and "Sieve of Eratosthenes". The first may be easier, but the second would run quicker for this particular problem of yours.

Functions in C

If you are learning C for the first time, you should check out some tutorials, e.g. https://www.tutorialspoint.com/cprogramming/index.htm.

Here is a link to the above mentioned site that focuses on the functions.


Update

Thank you for sharing your code below in the comments section.

I'll show you what I came up with utilizing the sieve of Eratosthenes.

The code is commented, but here are the highlights anyway:

  • Searching for primes until the square root of the number is reached.
  • The square root is approximated based on the Reverse Inverse Square Root technique. This is not accurate perfectly, but much faster than the regular (accurate) square root calculation.
  • Instead of printing all the found primes, I just print when the next 100,000 primes are calculated. (The reason is that printing to the console is time consuming.)
  • primes is initialized to be huge and the program may run out of memory (on the console!) before it reaches 100,000,000 primes.
  • The main code is highlighted, the rest is just helper methods.

So here's the code: 

#include <stdbool.h>
#include <stdio.h>
#include <xmmintrin.h>

static unsigned long long max = 0xFFFFFFFFFFFFFFFF; // The upper limit to check (N in the original description of the problem)
static unsigned long long primes[99999999];         // We store the already found primes here
static unsigned int next = 0;                       // The index of the next prime

// Approximates the squar root of a float using SSE
static inline void SSESqrt_Recip_Times_X(float * pOut, float * pIn)
{
   __m128 in = _mm_load_ss(pIn);
   _mm_store_ss(pOut, _mm_mul_ss(in, _mm_rsqrt_ss(in)));
   // compiles to movss, movaps, rsqrtss, mulss, movss
}

// Wrapper around the SSE rsqrtss for 64 bit unsigned ints
static inline unsigned long long SquareRootApprox(unsigned long long number)
{
    float f = (float)number;
    float squareRoot;
    SSESqrt_Recip_Times_X(&squareRoot, &f);
    unsigned long long squareRootApprox = (unsigned long long)squareRoot;
}

// Check if a specific number is a prim
static inline void CheckPrime(unsigned long long number)
{
    unsigned long long squareRootApprox = SquareRootApprox(number);
    
    for (unsigned int i = 0; i < next; i++) // Check for all known primes so far, if they are divisors for number.
    {
        if (number % primes[i] == 0)        // Found a divisor.
            return;                         // Not a prime. No need to check further.

        if (primes[i] > squareRootApprox)   // Passed the square root of the number. No need to check further.
            break;
    }

    primes[next++] = number;
    //printf("%u.\t--> %llu\n", next, number);
    if (next % 100000 == 0)
        printf("%u\n", next);
}

int main()
{
    for (unsigned long long i = 2; i < max; i++) // The first prime is 2. ;)
        CheckPrime(i);

    return 0;
}
commented May 18, 2021 by Peter Minarik (84,720 points)
I was a bit bored so I did (a version of ) the sieve of Eratosthenes. The program running on OnlineGDB can print the first 100,000 prime numbers in a few minutes. I'm working on some optimization too :)
I will post my code, after you've done yours. Just for comparison. If this is something of interest.
commented May 18, 2021 by Anitha (430 points)
I already wrote my code.I'm learning c-language now and I wrote a mistake in logic.I got it right now.Thankyou for your response.
#include<stdio.h>
primenumbers (int x);
main()
{
int n,x;
printf("enter a number");
scanf("%d",&n);
x=primenumbers (n);
}
primenumbers (int n)
{
int x,y,count=0;
for(x=1;x<=n;x++)
{
count=0;
for(y=1;y<=x/2;y++)
{
if(x%y==0)
{
count++;
}}
if(count==1)
printf("\n%d",x);
}}
I wrote like this.Is there anything to modify or can I write in a much simpler way?
commented May 18, 2021 by Peter Minarik (84,720 points)
edited May 19, 2021 by Peter Minarik
Yes. This code works. It seems to do the job.

However, the code is a bit ugly. For instance, you omit the return value of the functions (main, primenumbers). The default return value is int. It's not a good practice. You better specify your return value and if it's not void, add a return statement to your code.

#include <stdio.h>

void primenumbers (int x);

int main()
{
    int n;
    printf("enter a number");
    scanf("%d",&n);
    primenumbers(n);
    return 0;
}

void primenumbers(int n)
{
    int x, y, count = 0;
    for (x = 1; x <= n; x++)
    {
        count = 0;
        for (y = 1; y <= x / 2; y++)
        {
            if ( x % y ==0)
            {
                count++;
            }
        }
        if (count == 1)
            printf("\n%d",x);
    }
}

However, there is plenty of room for making the code run quicker, if this is something you are interested in.

For instance, instead of incrementing "count", you can just say: 'Hey, I've found a divisor. So this number cannot be a prime. Let's just stop right here and now.' All you need to do is to invoke the "break;" command.

And there are more to optimizations.

But yes, the code work. The logic is clear: A number is prime, if it has only one natural divisor: 1 (and itself, but you'll stop before reaching itself).

Good job! :)
commented May 18, 2021 by Peter Minarik (84,720 points)
edited May 18, 2021 by Peter Minarik
OMG. I've applied a bit of optimization.

Now, instead of finding the first 100,000 prime in a few minutes, a few seconds is enough for that.

Just before I'd print out the first 1,000,000 numbers, the program is shut down for using too much memory on the OnlineGDB server. :)

Instead just printing how many primes have been found (only print every whole 100,000) the first 1,000,000 primes are found in about 10 seconds.
0 votes
answered May 19, 2021 by rohan ag (1,310 points)
#include <stdio.h>

int main()
{
    int i,j,n;
     printf("enter n number");
     scanf("%d",&n);
     for(i=1;i<=n;i++)
     {
         for(j=2;j<i;j++)
         {
             if(i%j==0)
             break;
         }
         if(i==j)
         printf("%d ",i);
     }

    return 0;
}
–1 vote
answered May 19, 2021 by rohan ag (1,310 points)
#include <stdio.h>
void prime(int n)
{
    int i,j;
    for(i=1;i<=n;i++)
     {
         for(j=2;j<i;j++)
         {
             if(i%j==0)
             break;
         }
         if(i==j)
         printf("%d ",i);
     }  
}
int main()
{
    int n;
     printf("enter n number");
     scanf("%d",&n);
     prime(n);
   

    return 0;
}
0 votes
answered May 31, 2021 by bikash123-c (270 points)
#include<stdio.h>
#include<conio.h>
int main()
{
    int n,i,c=0;
    printf(" Enter any number :");
    scanf(" %d",&n);
    for(i=1;i<=n;i++)
    {
        if(n%i==0)
        {
            c++;
        }
    }
    if(c==2)
    printf(" number is prime");
    else
     printf(" number is not prime");
    
    
    
    return 0;
}
0 votes
answered Jun 6, 2021 by 20-1214 Adithya Galipelli (140 points)
#include<stdio.h>
void main()
{
    int n,i,j;
    printf("Enter n value\n");
    scanf("%d", &n);
    for(i = 1; i<=n; i++)
    {
        int count = 0;
        for (j =1; j<=i; j++)
        {
            if (i%j ==0)
            {
                count++;
            }
        }
        if(count ==2)
        {
            printf("%d ", i);
        }
    }
}
Welcome to OnlineGDB Q&A, where you can ask questions related to programming and OnlineGDB IDE and and receive answers from other members of the community.
...