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