Jump to content

Welcome to Geeks to Go - Register now for FREE

Geeks To Go is a helpful hub, where thousands of volunteer geeks quickly serve friendly answers and support. Check out the forums and get free advice from the experts. Register now to gain access to all of our features, it's FREE and only takes one minute. Once registered and logged in, you will be able to create topics, post replies to existing threads, give reputation to your fellow members, get your own private messenger, post status updates, manage your profile and so much more.

Create Account How it Works
Photo

Finding a prime number c++


  • Please log in to reply

#1
willmon2000

willmon2000

    Member

  • Member
  • PipPipPip
  • 215 posts
What im trying to do is have a number entered and have the program check if it is prime of not. Idea is call isprime from main and then have that it pass the number over to another function called checknum where if testnum % testnum -1==0 it prints number is prime and if testnumb % test numb >0 it should print out number is prime. i want a recursive function to decrease the number by one until one of the statements is true. here is what i have so far but still does not work.

#include <iostream>

using namespace std;


int testNum;
 int checknum (testNum)
    {
        if (testNum % testNum-1==0)
            cout << testNum "is not prime";

        if (testNum % testNum-1>0)
              cout<< testNum "is prime";
}
int isPrime ( int testNum )
{
     if (testNum== testNum)
     { cout << "The number " << testNum << "is prime"<<endl;
        return 1;}

        else checknum (testNum);
}


int main()
{
    cout << "Please enter a number" << endl;
    cin >> testNum;
    isPrime(testNum);
    return 0;
}

  • 0

Advertisements


#2
Spike

Spike

    nOoB

  • Member
  • PipPipPipPip
  • 1,355 posts

Sup willmon2000,

There are a number of loops (to make recursive) that you could of used in this example, mainly a for loop and a while loop. The best loop in this case would been the while loop as you would want it to exit straight away upon finding that it is definitely not a prime instead of continuation with the loop. Here is the revised code:
#include <iostream>

using namespace std;

bool isPrime(int tmpNum);

int main()
{
    int tmpNum = 0;

    cout << "Please enter a number" << endl;
    cin >> tmpNum;

    if (isPrime(tmpNum))
        cout << "The number " << tmpNum << " is prime" << endl;
    else
        cout << "The number " << tmpNum << " is not prime" << endl;

    return 0;
}

bool isPrime(int tmpNum)
{
    int divNum = tmpNum - 1;
    bool remainder = false;

    if(tmpNum == 2)
        return true;

    while(divNum > 1)
    {
        if(tmpNum % divNum > 0)
            remainder = true;
        else
            return false;

        divNum--;
    }

    return remainder;
}

I have also created another function to go along in your program if need be, this will list all prime numbers; Where lNum is the number you would like to check up until. (I have used a for loop in this function so you can see the use of both of them, but I recommend the use of a while loop in the above function)
void listPrimes(int lNum)
{
    for(int i = 0; i <= lNum; i++)
    {
        if(isPrime(i))
            cout << "The number " << i << " is prime" << endl;
    }        }

I hope you found this code useful... If you need any explanation of how any of it works, don't hesitate to ask. Also I was just wondering did you find my response in this topic "Divisible or not, nested if statements" useful?


Peace Out :cool:


  • 0

#3
AceInfinity

AceInfinity

    Visiting Staff

  • Visiting Consultant
  • 34 posts
  • MVP
What spike_hacker_inc provided you is nice, although you really only have to check up to the square root of the original number. And you should not have to check for it being divisible by any even number if you've already checked the input to be an odd number (with the exception of 2); that simply doesn't make sense.

Here's what I wrote in C#, just as an example:
private void button1_Click( bject sender, EventArgs e)
{
	UInt64 x = 10000000000000000001;
	MessageBox.Show(x + (IsPrime(x) ? "is a prime" : "is not a prime"));
}

private bool IsPrime(UInt64 input)
{
	if(input == 2) return true;
	if(input == 1 || input % 2 == 0) return false;

	for(UInt64 n = 3; n < Math.Sqrt(input); n += 2)
	{
		if(input % n == 0 && n != input) return false;
	}
	return true;
}

Doing this:
while(divNum > 1)

Would take a long time...

*Note: Keep in mind, 0 is also not a prime number but considered a "Special" number

Edited by AceInfinity, 06 May 2012 - 02:55 AM.

  • 0






Similar Topics

0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users

As Featured On:

Microsoft Yahoo BBC MSN PC Magazine Washington Post HP