I need to output in four columns.
1) The first will contain n.
2) The second will contain pi(n)
3) The third will contain n/ln(n)
4) The fourth will contain the ration of pi(n) to n/ln(n).

``````#include <stdio.h>
#include <string.h>
#include <stdint.h>

#define MAXN  100000000  /* maximum value of N */
#define P1    1562501    /* = ceil(MAXN/64) */
#define P2    50000000   /* = ceil(MAXN/2) */
#define P3    5000       /* = ceil(ceil(sqrt(MAXN))/2) */

uint32_t sieve[P1];

#define GET(b) ((sieve[(b)>>5]>>((b)&31))&1)

void make()
{
uint32_t i, j, k;
memset(sieve, 0, sizeof(sieve));
for (k = 1; k <= P3; k++)
if (GET(k)==0) for(j=2*k+1,i=2*k*(k+1);i<P2;i+=j) sieve[i>>5]|=1<<(i&31);
}

int isprime(int p) { return p==2 || (p>2 && (p&1)==1 && (GET((p-1)>>1)==0)); }

int main()
{
int i, n;
make();
for (n = 0, i = 0; i <= MAXN; i++)
if (isprime(i)) n++;
printf("The number of primes below 10^8 is %d.\n", n);
return 0;
}
``````
2
Contributors
4
Replies
41
Views
5 Years
Discussion Span
Last Post by mical700

So, what is the problem? You stated the objective of the program but didn't tell us what's wrong with the code you posted.

Sorry. The code is ok.
The program to compute pi(n), which is the number of prime numbers < n. It will print out pi(n) for values of n that are powers of 10 from 10 to 10^8.
For example, pi(2) = 1 and pi(10) = 4.1

Output will be in four columns.
1) The first will contain n.
2) The second will contain pi(n)
3) The third will contain n/ln(n)
4) The fourth will contain the ration of pi(n) to n/ln(n).
An extremely important theorem of number theory says that as n goes to pi, the ratio of pi(n) to n/ln(n) converges to 1.

So what should I do to output as above?
Thanks'

Edited by mical700: modified

You need to write a function named pi so that it can calculate pi(x) Or does that mean pi as in the circumference of a circle (3.14...) ? Same with the function ln()

If the array is correctly calculated outputting the result is trivial -- just call printf() in a loop

line 21: make it easy on yourself and put a couple carrage returns in that line, split up the statements instead of putting them all on the same line. For example the following is much easier to read.

``````if (GET(k)==0)
{
for(j=2*k+1,i=2*k*(k+1);i<P2;i+=j)
sieve[i>>5]|=1<<(i&31);
}
``````

Edited by Ancient Dragon

Thanks'.