Prime Number Program

Hello everyone. this is my first post here. I am working on a prime number program that will output all primes from 1 to 100,000. I have the program working and running. It is to calculate the prime numbers and print seven per line. As of now it is printing a 0 for all non prime number instead of omitting them.
I am using code blocks software.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<iostream>
#include<cmath>

using namespace std;

int main()
{
int num[100000], i, j;

for(i=0;i<=100000;i++)
num[i]=i+1;

for(i=1;i<=100000;i++)
  {
    if(num[i]!=0)
    {
        for(j=(i+1);j<=100000;j++)
      {
             if(num[j]!=0)
          {
                 if((num[j]%num[i])==0)
                 num[j]=0;
          }
      }
    }
  }

for(i=0;i<=100000;i++)
    {

       cout << num[i] << " ";
       if((i+1)%7==0)
        cout << endl;

    }
}


from line 28
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
j = 0;
  for( i = 0; i <= 100000; i++)
  {
    if(num[i])
    {
      cout << num[i] << " ";
      ++j;
    }

    if(j == 7)
    {
      j = 0;
      cout << endl;
    }
  }

There are a lot of ways to find the prime numbers
Sieve of Eratosthenes is one of them, you could try it if you liked to
Besides, your code still have some space to improve, try to find out by yourself
And please no questions asked on why I did it this way. It's fast and that's all that matters. The only problem is that you might get one prime number over the value you want but... that's the only problem with it.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

#define MAXNUMBER 100000

bool prim(int nr);

vector<int> prim_numbers;

int main()
{
	prim_numbers.push_back(2);
	prim_numbers.push_back(3);

	for(int i = 6; i<MAXNUMBER; i+=6)
	{
		if(prim(i-1))
		{
			prim_numbers.push_back(i-1);
		}

		if(prim(i+1))
		{
			prim_numbers.push_back(i+1);
		}
	}



	for(unsigned int i=0; i< prim_numbers.size(); i++)
	{
		cout<<prim_numbers[i]<<"  ";
		if(!((i+1)%7))
		{
			cout<<endl;
		}

	}

	return 0;
}

bool prim(int nr)
{
	double root;

	root = sqrt(nr + 0.0);

	int size = prim_numbers.size();

	for (int i = 0; i < size && prim_numbers[i] <= root; i++)
	{
		if(nr % prim_numbers[i] == 0)
		{
			return false;
		}
	}
	return true;
}
Last edited on
What's the point of posting? are you asking us to review it? refine it? etc?

I'm going to look up an algorithm for finding prime numbers and make a program....

I think there's a recurring function that will find prime numbers. I don't exactly remember it, but I think it's much more efficient. I will post back before the day's over.
Last edited on
prime numbers,
I remember writing one in BASIC on my old Dragon 32 computer back in the 80s.
(that's 32Kb RAM, sonny)
it slowed down after about 100 or so.

1MHz processor
8 bit

you kids don't know your born
<sucks on pipe>

then the psion organizer of course
<sucks on pipe>
bigearsbilly, haha I wonder how much that thing cost you...

I'm running on quad 2.4ghz with 8gigz of ram... This is my first desktop; its emazing how far we've come...
Last edited on
i haven't tested this code for errors etc etc... as my eyeballs are on the brink of shutting down...
you'll still be able to get the gist of it though.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <cmath>
using namespace std;
#define MAX 100000

int main()
{
	int array[MAX];
	for(int a = 0; a <= MAX; a++)
		array[a] += a+1;

	for( int j = 1, j<= MAX; j++)
	{
		int i = 2;
		while ( i <= sqrt(static_cast<double>(array[j]));
		{
			if (array[j] % i != 0)
				array[j] = 0;
			i++;
		}

	}

	for(int a = 1; a <= MAX; a++)
	{
		cout << array[a] << " ";
		if (!(a%7))
			cout << endl;
	}

	return 0;
}


the method is from C++ Without Fear -- it's modified though... as if (array[j] % i != 0) would be if (array[j] % i == 0) and that would tell if it's not prime while mine tells that it is in fact prime... which i'm not sure is actually correct..
Last edited on
This is the output for my program for MAXNUMBER 200. It really works. So you can use it.

1
2
3
4
5
6
7
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  Press any key


And why I did the +=6 thing? It's because of this
2 is prime
3 is prime
4 is not because %2
5 is prime
6 is not because %2 and %3
7 is prime
now I skipped to 12 and checked 12-1 and 12+1
8 and 10 are not because % 2
and 9 is not because % 3
skip to 18
14 and 16 are not because %2
15 is not because % 3
And all the numbers are like this. So it's useless to check them all. You increment with 6 and you check the one before and the one after. Then you increment again with 6 and repeat.

Sorry for my bad way of explaining things. I'm not good at explaining things. I just hope you got it.
Last edited on
You may still want to be doing something about <math.h> and your global variable, though.
The thing with math.h is for sqrt. You only need to check a number untill you reach sqrt of that number so if you know a better way to compute sqrt of a number, get rid of <math.h> and use that.
It's not about sqrt. It's that you should it include it as: #include <cmath>
I have edited it. :) Better now? :)
Better already. :P
Topic archived. No new replies allowed.