Associated Topics || Dr. Math Home || Search Dr. Math

### Writing a Program to Generate Primes

```
Date: 12/5/95 at 17:21:52
From: Anonymous
Subject: prime numbers

I need a list of the first 100 prime numbers and a way of
generating them.  I hope you will help me!

Thank you,
Bonnie Thurber
```

```
Date: 3/17/96 at 22:47:6
From: Doctor Jodi
Subject: Re: prime numbers

There is a list of first 10,000 primes at

http://www.utm.edu/research/primes/lists/small/10000.txt

-Doctor Jodi,  The Math Forum
```

```
Date: 3/20/96 at 0:36:45
From: Doctor Patrick
Subject: Re: prime numbers

Hi--

The first 100 primes are
2  3  5  7  11  13  17  19  23  29  31  37  41  43  47  53  59
61  67  71  73  79  83  89  97  101  103  107  109  113  127   131
137  139  149  151  157  163  167  173  179  181  191  193  197
199  211  223  227  229  233  239    241  251  257  263  269  271
277  281  283  293  307  311 313  317  331  337  347  349  353
359  367  373  379  383  389  397  401  409  419  421  431 433
439  443  449  457  461  463    467  479  487  491  499  503  509
521  523 541.

The easiest way to generate them is to use a computer program
which tests each number to see if it can be factored by any number
up to and including that number's square root.  You can stop at
the square root, since all other combinations of factors would
include one number larger than the square root, and one smaller.
Once you have gone through the smaller numbers it would be
redundant to check the larger halves as well.

Actually, you would only have to check a number by all of the
primes up to its square root (Do you understand why?), but that
would take more programming skill than I have at the moment.  If
you need more detailed information, take a look at

http://www.utm.edu/research/primes/prove/

I'm attaching the program I used to find these 100 primes.  It's
written in c++, but uses entirely straight c, except for the
sqrt() function.

#include <stdio.h>
#include <math.h>

main ()
{
int num, count, i, prime;

num =2;
for (count=0; count<100; num++) {  /* keep track of primes
found, stop at 100, increase the value of the number tested */

prime=1;   /* prime keeps track of if a number is
found to be prime or not--1=prime 0=not prime /*

for (i=2; i<=sqrt(num); i++)
if (num%i==0) prime=0;  /*test to see in
num is prime */
if (prime!=0) {
printf("%d ", num); /* print primes */
count++;} /* inclease count of primes
found */
}
}

-Doctor Patrick,  The Math Forum

```
Associated Topics:
High School Calculators, Computers

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search