0 votes

Best answer

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. :(

Here are some pointers that may help you

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.

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.

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; }

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?

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

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! :)

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! :)

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.

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

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

}

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

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

}

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;

}

...

I will post my code, after you've done yours. Just for comparison. If this is something of interest.