How to easily calculate the first 180 prime numbers with a C or C++ program!

charlie.wilson (63)in #programming • 9 years ago

Have you ever tried to count as high as you can in prime numbers? How high did you get? I bet a computer can count higher than you! I know... That isn't even fair! Look on the bright side though, we have technology to do all of these hard math calculations for us. I wrote a program today that lists the first 180 prime numbers. It can easily be altered to count as high as you want though. My program is on C++, but it can be easily altered for C (just don't declare any variables inside the parameters of the for loops and it is a working C program).

Here is how my program works in a nutshell:

Stores all integers in an int array
Checks to see if each integer is divisible by any integers between 1 and itself (exclusive -- prime numbers are divisible by 1 and themselves)
If so, store the number in an array and print the array

Here is the program:

#include<stdio.h>

int main()
{
    int integers[1062];
    int primes[180] = {1,2};

    for(int x = 0; x < 1062; x++)
        integers[x] = x+2;

    for(int x = 0; x < 1062; x++)
    {
        for(int y = 0; y < x; y++)
        {
            if(integers[x] % integers[y] == 0)
                break;
            if(y == x - 1)
                for(int z = 0; z < 180; z++)
                    if(primes[z] == 0)
                    {
                        primes[z] = integers[x];
                        break;
                    }
        }
    }
    for(int x = 0; x < 30; x++)
        if(primes[x] != 0)
            printf("%8d %8d %8d %8d %8d %8d\n",primes[x], primes[x+30], primes[x+60], primes[x+90], primes[x+120], primes[x+150]);

    return 0;
}

A deeper explanation:

int integers[] --> an array to hold all integers
int primes[] --> an array to hold all of the prime numbers
set the first two values of primes to 1 and 2 (the first two primes) and the rest will be automatically set to 0
set integers to values 2 - 1063 in order
use nested for loops so we can compare every integer with every other integer larger than 1 and less than itself (notice y < x on the second for loop -- we don't want to modulo the integer by anything larger than itself)
if(integers[x] % integers[y] == 0) --> if the remainder is 0, then the integer is divisible by another integer (so it is NOT prime)
break to skip this integer
if(y == x - 1) --> if this is the last int to be compared (if we get to this on the last iteration, we know that the number must be prime -- it wasn't divisible by any other integer)
find the first free slot in primes (the first 0) and place the prime number in there
break out of the loop so the number doesn't get place in primes more than once
print 6 columns with 30 prime numbers each (180)
I used printf() because it was easier to neatly format than cout (%8d allows me to print an integer in an amount of 8 spaces -- this lines up the output very well considering not all the numbers have the same amount of digits)

The output:

[cmw4026@omega test]$ g++ primes.cpp
[cmw4026@omega test]$ ./a.out
       1      113      281      463      659      863
       2      127      283      467      661      877
       3      131      293      479      673      881
       5      137      307      487      677      883
       7      139      311      491      683      887
      11      149      313      499      691      907
      13      151      317      503      701      911
      17      157      331      509      709      919
      19      163      337      521      719      929
      23      167      347      523      727      937
      29      173      349      541      733      941
      31      179      353      547      739      947
      37      181      359      557      743      953
      41      191      367      563      751      967
      43      193      373      569      757      971
      47      197      379      571      761      977
      53      199      383      577      769      983
      59      211      389      587      773      991
      61      223      397      593      787      997
      67      227      401      599      797     1009
      71      229      409      601      809     1013
      73      233      419      607      811     1019
      79      239      421      613      821     1021
      83      241      431      617      823     1031
      89      251      433      619      827     1033
      97      257      439      631      829     1039
     101      263      443      641      839     1049
     103      269      449      643      853     1051
     107      271      457      647      857     1061
     109      277      461      653      859     1063
[cmw4026@omega test]$

I hope this was useful! Leave any suggestions in the comments.

On a side note, @dwinblood makes really great game development tutorials using Unity. Definitely check him out if you are interested in that.

Also, I have my own beginner friendly tutorial series:

Part 1: Hello World!

Part 2: Variables

Part 3: Functions

Part 4: if(), else, else if()

Part 5: Loops

Part 6: Arrays

Part 7: Basic Input/Output

Part 9: Sorting Arrays

Part 10: Random Numbers