# C program to display prime numbers between 1 to n

With the use of functions

answered May 18 by (34,450 points)
edited May 18 by Peter Minarik

# 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

## 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

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;         // 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)
{
_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 by (34,450 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 by (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>
main()
{
int n,x;
printf("enter a number");
scanf("%d",&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 by (34,450 points)
edited May 19 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>

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

{
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 by (34,450 points)
edited May 18 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.
answered May 19 by (1,270 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 by (1,270 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;
}
answered May 31 by (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;
}
answered Jun 6 by (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);
}
}
}