PRIME_NUMBER
Program to Count Primes

PRIME_NUMBER is a C program which counts the number of primes between 1 and N.

The algorithm is completely naive. For each integer I, it simply checks whether any smaller J evenly divides it. The total amount of work for a given N is thus roughly proportional to 1/2*N^2.

This program is mainly a starting point for investigations into parallelization.

Here are the counts of the number of primes for some selected values of N:

N	Number of Primes
1	0
10	4
100	25
1,000	168
10,000	1,229
100,000	9,592
1,000,000	78,498
10,000,000	664,579
100,000,000	5,761,455
1,000,000,000	50,847,534

The following results were observed for the elapsed time.

N	Pi	Time
1	0	0.000030
2	1	0.000016
4	2	0.000016
8	4	0.000017
16	6	0.000020
32	11	0.000030
64	18	0.000057
128	31	0.000147
256	54	0.000452
512	97	0.001548
1024	172	0.005303
2048	309	0.018660
4096	564	0.068059
8192	1028	0.246378
16384	1900	0.914953
32768	3512	3.380086
65536	6542	12.619071
131072	12251	47.412759

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Related Data and Programs:

COLLATZ, a MATLAB library which computes and analyzes the Collatz sequence (or "hailstone" sequence or "3n+1 sequence");

MD is a C program which carries out a molecular dynamics simulation, and is intended as a starting point for implementing a parallel version.

PRIME_NUMBER is available in a C version and a C++ version and a FORTRAN77 version and a FORTRAN90 version and a MATLAB version.

PRIME_NUMBER_MPI is a C program which counts the number of primes between 1 and N, using MPI for parallel execution.

PRIME_NUMBER_OPEN_MP is a C program which counts the number of primes between 1 and N, using OpenMP for parallel execution.

SATISFIABILITY is a C program which demonstrates, for a particular circuit, an exhaustive search for solutions of the circuit satisfiability problem.

TIMER is a directory of C programs which demonstrate how to compute CPU time or elapsed time.

Reference:

1. Eratosthenes,
   A Method For Finding Prime Numbers,
   Papyrus 487.

Source Code:

• prime_number.c, the source code.
• prime_number.h, the include file.
• prime_number.csh, commands to compile the source code.

Examples and Tests:

• prime_number_prb.c, a sample calling program.
• prime_number_prb.csh, commands to compile and run the sample program.
• prime_number_prb_output.txt, the output file.

List of Routines:

• PRIME_NUMBER returns the number of primes between 1 and N.

You can go up one level to the C source codes.