Trouble with the logic of Prime numbers in a certain program.

tylerfelix · #1 30-Oct-2005, 17:12

Ok I want to build a C++ program that can do the things below:

Accepts a number between 1 and 32000.
Determines whether the number is a product of two distinct primes. You must use the isPrime function from my previous thread.
If answer to 3 is yes, then displays the two prime numbers.
If answer to 3 is no, displays a message saying that "The number NNNN is not a valid public key".

I've done finding prime numbers themselves, but never the steps afterward.. view my previous started thread to get a feel for what I mean.

examples of output from input are:

Enter an integer: 75
The integer 75 is not a valid public key.
Check another integer? (y/n): y

Enter an integer: 707
707 is a valid public key; it is a product of the prime numbers 7 and 101.
Check another integer? (y/n): y

Paramesh · #2 02-Nov-2005, 03:15

Hi tyler,

You can use the do while loop to get the input from the user whether the user wants to continue or not..
for example,

CPP / C++ / C Code:

char input = 'y';
do
{

//code..

cout << "Do you want to continue? (y/n) ";
cin   >> input;
} while ( input == 'y' || input == 'Y');

Now, to the main part of the function:
I thought of an idea like this:
1. Use a for loop and make a variable i vary from 2 to the number given(say num).
i.e

CPP / C++ / C Code:

    for(i = 2 ; i < num; i++ )
    {

2. Check whether num % i == 0.

CPP / C++ / C Code:

        if(num % i == 0)
        {

3. If it is true, then check whether both i and num / i (factors) are primes using the isPrime function.

CPP / C++ / C Code:

             if( isPrime( i ) && isPrime( num / i ))
             cout<<"The prime factors are.." << i <<" and "<< num / i <<endl;

4. If it is true, then display the values and display that the value num is a public key.

Now on to improving the isPrime function.
We use bool as the return type.

We can reduce the number of loops by checking whether the number is divisible by 2 at the starting itself. Then we can check by dividing the num by odd numbers only.
Here is the modified code:

CPP / C++ / C Code:


bool isPrime(int num)                  //note that we have the value of numberPrime in the variable num
{
   int i;
 
   if(num % 2 == 0)                    //check at start itself       
   return false;                       //return false if divisible by 2
  
   for( i = 2 ; i < num / 2; i+=2 )   //for loop. note that i+=2. We are checking by odd numbers only
   {
      if ( num % i == 0)             //check whether remainder is zero
      {
         return false;               //return false if there is no remainder
      }
   }
   return true;                      //if all of these things fail, return true. ie the number is prime.         

}

Read the comments for more information.

Regards,
Paramesh.

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Linear Search	eccoflame	C Programming Language	3	19-Apr-2005 08:36
Amicable numbers program	noamfrie	C Programming Language	1	06-Dec-2004 07:55
prime numbers	quasimof	C++ Forum	1	01-Nov-2004 19:35
Need help with my programs, please help.	agentxx04	C Programming Language	1	23-Sep-2004 18:02
Help w/ prime # determination	crystalattice	C Programming Language	17	18-Apr-2004 21:43

Trouble with the logic of Prime numbers in a certain program.

Re: Trouble with the logic of Prime numbers in a certain program.