Prime number calculator

Hi,

I just need some help with creating a prime number calculator. Idea is user enters a number, say 10 & all prime numbers up to that input number will be calculated & only prime numbers will be displayed.

Does anybody have an idea of how I should go about this?

Thanks for any responses
First of all you need to know what a prime number is... Then it probably requires a loop.

It's easy to implement one for a school assignment or something, but if you require good performance you may consider implementing the Sieve of Eratosthenes using a bitset or vector<bool>.
First of all you need to know what a prime number is... Then it probably requires a loop.

It's easy to implement one for a school assignment or something, but if you require good performance you may consider implementing the Sieve of Eratosthenes using a bitset or vector<bool>.
I was thinking something along the lines of a for loop that loops up until the answer and another for loop that loops up to possibly one before the original for loop.

So x = original for loop
& y = for loop that goes up to x - 1 (in value as an integer)

the int valid = x % y

if (valid > 0) // has a remainder
z++ // if it is less than x & not only 1 less

if (valid == 0)
//obviously not a prime number...


but I don't really know how to go about putting all this into code. I pretty much just started c++, so I just need a bit of guidance.

Thanks for you input ! :)

btw this is just for like a little project i awnt to do myself, not a crazy high performance calculator...yes I'm noob lol
Last edited on
Ok, great.

so far you have...

1
2
3
4
5
6
for(  ; ; )
{
  for( ; ; )
  {
  }
}


nested for loops.. Well, I will tell you there are infinite ways to code this. But, a function like:
 
bool isPrime(int number)
will probably be very handy for this assignment because it will reduce the complexity assuming you can use functions. The function would of course test the argument for being prime and return true/false.
Last edited on
I don't know how to use bool yet, but I was thinking something along the lines of:

//headers etc

int i = 2;
int z = 1;
int answer;
int isprime = 20; // 10 will equate to false condition & 20 to true

cout << "Please enter a number: ";
cin >> answer;

for (i; i< answer; i++)
{
for (z; z < i; z++)
{
int valid = i % z;

if (valid > 0)
z++

if (valid == 0)
cout << i << " is a prime number";
}
}

what do you think of that?




[code] Your code goes here [/code]
1
2
3
4
5
6
7
8
for (z /*this doesn't do anything*/ ; z < i; z++)
{
  int valid = i % z;
  if (valid > 0)
    z++; //what do you want to do with this?
  if (valid == 0)
    cout << i << " is a prime number"; //actually the opposite 
}
Hi everybody, I just finished a little program with templates and I think is a good place to share it with other C++ loved guys, it uses meta programming and I know that is is already done before me by others, maybe my solving way is my little bit contribution, ok so if you want to see that a number is prime or not .....

#include "stdafx.h"
#include <iostream>
using namespace std;

template<int a, int b> struct notDivided
{
enum {result = a % b};
};

template<int a, int b> struct prim
{
enum {result = notDivided<a, b>::result && prim<a, b - 1>::result};
};

template<int a> struct prim<a, 1>
{
enum{result = 1};
};

template<int a> struct Prim
{
enum {result = prim<a, a - 1>::result ? 1 : 0};
};

int _tmain(int argc, _TCHAR* argv[])
{
cout << boolalpha << (bool)Prim<100>::result << " " << (bool)Prim<101>::result;
cin.ignore();
return 0;
}

I awaiting your impressions / br

Hi guys, another solution , I finished this in a quarter of hour and I tested it and works pretty well, have fun with it:

#include "stdafx.h"
#include <iostream>
#include <cmath>
using namespace std;

//costica1@yahoo.com (Agavriloaie Constantin)
int _tmain(int argc, _TCHAR* argv[])
{
unsigned number;
cout << "Input the number: ";
cin >> number;

if(number == 1 || number == 0) // one isn't prime and also one isn't compound
{
cout << "there aren't any prime number" << endl;
cin.ignore();
return 0;
}

for(unsigned n = 2; n <= number; n++)
{
bool prime(true);
unsigned sq = (unsigned)sqrt((double)n) + 1;
for(unsigned div = 2; div < sq; div++)
if(!(n % div))
{
prime = false;
break;
}

if(prime)
cout << n << " ";
}

cin.ignore();
return 0;
}
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
#include "stdafx.h"
#include <iostream>
#include <cmath>
using namespace std;


int _tmain(int argc, _TCHAR* argv[])
{
	unsigned number;
	cout << "Input the number: ";
    cin >> number;

	if(number == 1 || number == 0) // one isn't prime and also one isn't compound
	{
		cout << "there aren't any prime number" << endl;
		cin.ignore();
		return 0;
	}

	for(unsigned n = 2; n <= number; n++)
	{
		bool prime(true);
		unsigned sq = (unsigned)sqrt((double)n) + 1;
		for(unsigned div = 2; div < sq; div++)
			if(!(n % div))
			{
				prime = false;
				break;
			}

		if(prime)
			cout << n << " ";
	}

	cin.ignore();
	return 0;
}
Testing for division up to sqrt(n)+1 is also an optimization.

Making it multi-threaded is also another possible optimization if your processor has more than one core, I have used the same algorithm as you have using two threads at a time and it will blow a single threaded app out of the water if you have a 2 core processor.
Another optimization will be just testing for division against prime numbers (that were already found out)
Topic archived. No new replies allowed.