C++ Code for prime numbers

[autumnreneem]

As a new user of c++ and windows visual c++, I need help with my homework.

I need to write a program that finds all of the prime numbers between 3 and 100. I understand I need to use a nested loop. The first asking if the number is from 3 to 100, and then if it is, is it prime?
I need helping writing an equation to put in the second loop that will find if the number is prime. Perhaps an equation that takes the number and divides it by 2?

Help please!

[georgep]

So, firstly, define a prime number carefully.

>an integer that has no integral factors but itself and 1

So what does that mean exactly? Well, when you divide it by any whole number other than itself and 1, you will never get a remainder.

So there you go: you need to (and I suggest using a loop) check all the numbers from 2 to your number and if dividing your number by one of these numbers has a remainder of 0, it isn't prime.

There are a couple of things I have intentionally left out. It is your homework after all. I suggest using a function to check numbers (starting at 3, ending at 100) and if it is prime then display it.

If you are stuck or need any more help, feel free to ask.

[3hM2Nwbp]

This should get you started.

#include <iostream>
enum NumberType
{
	PRIME,
	COMPOSITE,
	NEITHER
};

NumberType getNumberType(unsigned int number)
{
	if(/*the number is less than 2*/) return NEITHER;
	if(/*the number is divisible by 2*/) return COMPOSITE;
	for(/*every odd number, N, from 3 to (number / 2)*/)
	{
		if(/*the number is divisible by N*/)
		{
			return COMPOSITE;
		}
	}
	return PRIME;	/* The provided number is greater than 2, and is only divisble by 1 and itself */
}

int main()
{
	int primeSuspect;
	std::cin >> primeSuspect;
	NumberType type = getNumberType(primeSuspect);
	std::cout << "The prime suspect has been found: " << ((type == PRIME) ? "Guilty" : "Innocent");	
}

[GRex2595]

The maximum test number should be no bigger than half of the number you are trying to find prime or not. If the test number exceeds 1/2 of the prime number without hitting a remainder zero then it is prime. If a number is not divisible by two, then it is not divisible by any number that is divisible by two.

27 / 2 = 13 //truncating the value

Any numbers greater than 13 will not go evenly into 27.

27 % 2 != 0 therefore 27 % (2 * x) != 0

Numbers indivisible by two will be indivisible by 2 * any number.

[georgep]

I was hoping autumnreneem would notice this. However, the highest you have to go is NOT half, it is the square root.

With addition, if you are making pairs that add up to a number you only need continue up to half, because at half the 2 numbers you add together make your number. After half, you start repeating pairs you have already made.

With multiplication, you only need go up to the square root, because the root multiplied by the root is the number. Then, you begin repeating pairs.

I would normally go along with the half, or even just going up to the number itself, for a number as small as 100. However, I was working on a problem a while back that required I find factors, or more specifically, a triangle number with 500 of them. Without the use of only going up to the square root, my program took hours. With the use of it, my program took a few seconds.

With large numbers eg. 100,000,000,000 going up to the root instead of half / the number itself saves you 40,000,000,000 and 90,000,000,000 checks respectively.

[GRex2595]

Yeah. I forgot about square roots. I was only thinking about two times a number only needs to be checked twice, but if you want twelve, then you can check 3 * 4 twice without going over 6.

[autumnreneem]

Luc,

Okay. I somewhat understand. But I totally do not understand the concept.

I've been searching tis for almost a week now and I cant find anything that makes me get it. In my past assignments Ive always used int main (), and I understood how to assign variables and what not. I understand using if, and if else, etc.

I do not understand how I am supposed to ask the user to enter a number, then use cin << user_req_num to use this variable in my equations to see if it is a variable of prime or not.

Help?

[scarywoody]

Hello I am new to the forum and had a similar problem. The code posted below is not my work, and I am currently searching for the source to give credit. I made a few minor tweaks to the code. I am also new to CS and this made sense to me, so maybe this code will make a little more sense to you :)

#include<iostream>

using namespace std;

int main()
{

	int num, count, check = 0;	
	cout<<"Please enter an integer: ";
	cin>>num;
 
	if(num <= 1)	//1 is not a prime number
	{
		cout<<"The number you entered is not a prime number. "<<endl;
		system("pause");
		exit(0);
	}

	if(num == 2)	//Displays 'Number is Prime' and ends the program if the number is 2
	{
		cout<<"2 is the only even prime number. "<<endl;
		system("pause");
		exit(0);
	}
 
	for(count = 2; count<num; count++)	//Loop to divide the number by every number from 2 to (num-1)
	{
		if(num % count == 0)	//Statement to change the variable 'check' to 1 if the number gets divided
		{
			check = 1;
		}
	}
 
	if(check == 0)	//Statement to check if the 'check' variable has changed
	{
		cout<<"The number you entered is a prime number. "<<endl;
	}
	else
	{
		cout<<"The number you entered is not a prime number."<<endl;
	}

	system("pause");
	return 0;
}

[scarywoody]

Found the source:

http://www.mycoding.net/2011/02/c-program-to-check-if-a-number-is-a-prime-number/