Prime Numbers

[Neil010]

Hello Everybody, I am trying to find the largest prime factor of a number. But when I am trying to determine if a number is a prime number in the function:
int is_prime(int number), I am unable to exit the loop.

Help is greatly appreciated!!

Here is the code:

#include<iostream>
using namespace std;

int is_prime(int number) //the problem is in this function
{
     int num = number;
     int factor=0;
     do{
          num++;
          for(int i=1;i<(num+1);i++){
          if(num % i == 0)
          factor++;
          }
     }while(factor!=2);
     return num;
}
int main()
{
    
    int prime,factor,divisor, new_divisor, large;
    divisor = 2;
    large = 2;
    prime = 20; //for example
    int counter = 0;
    do
    {
        counter++;
        cout<<counter<<endl<<endl;
          if(prime % divisor == 0) //condition 1
          prime /= divisor;
          else if(prime % divisor != 0)
          new_divisor = is_prime(divisor);
          
          if(new_divisor>divisor)
          large = new_divisor;
          
          divisor = new_divisor;
    }while (prime != 0);
    cout<<large;
    system("pause");
    return 0;
}

So when the program runs, it first divides 20 by 2, to get 10, then divides 10 by 2 to get 5. Since, // condition 1 is not met, it passes 2 to the function int is_prime(int number). The function is able to return 3, but cannot exit the loop when num is 4.

I think the problem lies in the function: int is_prime(int number).

Thanks once again!!

[Duthomhas]

Throw away all code that someone else gave you. You can see why is_prime() fails here:

int is_prime(int number) //the problem is in this function
{
     int num = number;
     int factor=0;
     do{
          num++;
          for(int i=1;i<(num+1);i++){
cout << "\n(num, i) = (" << num << ", " << i << ")\n" << flush;
          if(num % i == 0)
          factor++;
cout << "(factor = " << factor << ")\n" << flush;
          }
     }while(factor!=2);
     return num;
}

I suspect that someone gave you that code, though. And yes, it is broken.


You would have a much easier time doing this straight yourself. You will need:

  • The potentially prime number. (You call this prime.)
  • A divisor/counter variable to loop from 2 to (prime - 1).

That second part is where you are having trouble. Remember, to check to see if 7 is prime (for example), start with

  • prime = 7
  • divisor = 2 (all numbers are evenly divisible by one, so we start at two)

If 7 mod 2 is 0 then we know the number is not prime.

But since 7 mod 2 is 1 we cannot yet say that the number is not prime. (It might be, but it might not -- we don't yet know.)

  • divisor++

Again, if 7 mod 3 is 0 then we know the number is not prime.

But since 7 mod 3 is 1 we still cannot say we know anything about the primality of 7. If we keep going, we also learn that:

  • 7 mod 4 ≠ 0
  • 7 mod 5 ≠ 0
  • 7 mod 6 ≠ 0

At this point, divisor == prime. We did not find any numbers that evenly divide into prime (except for 1 and prime, which we know do evenly divide it), so we can safely conclude that the number is actually prime.

If we start with, say:

  • prime = 55

Then:

  • 55 mod 2 ≠ 0
  • 55 mod 3 ≠ 0
  • 55 mod 4 ≠ 0
  • 55 mod 5 = 0 (ah ha!)

Since 55 is evenly divisible by 5, and 5≠1 and 5≠55, we know that 55 cannot be a prime number. We'll just return out of our loop.


Now that you've thought this through, put it all in a function:

bool is_prime(int prime)
{
    int divisor = 2;

    /* see note below */

    while (divisor < prime)
    {
        if ( /* what is my test for not-a-prime? */ )
        {
            return false;
        }
        /* what do I do to divisor here? */
    }

    return true;
}

Here is the note: make sure to check that the value of prime is greater than one before entering the loop, otherwise you will be stuck in a really long loop while we wait for 2++ to become greater than or equal to -7, for example.

Now, to use the function, just call it:

int main()
{
    int n;
    cout << "What number would you like to test for prime? " << flush;
    cin >> n;

    if (is_prime(n))
    {
        cout << "prime\n";
    }
    else
    {
        cout << "not prime\n";
    }
    system("pause");
    return 0;
}

Additional Notes

You need to pay special attention to indentation. Only indent lines that are somehow directly dependent on the less indented line above it. For example, you have lines 29 and 30 indented underneath line 28. But removing line 28 does not change how lines 29 and 30 work. 29 should be only indented as far as 28.

Line 30, however, is dependent on line 29. Line 30 should be indented further than 29.

        cout<<counter<<endl<<endl;
        if(prime % divisor == 0) //condition 1
          prime /= divisor;  /* <-- what is this supposed to do? (What did you learn from line 29?) */

Hope this helps.

[tcs]

1. Take a piece of paper.
2. Draw a table. Each column represents one of your variables.
3. The tables first row contains the initial values of your variables.
4. Each following row may represent an execution step of your program which modifies a variable.
5. Now step through your program writing down each actual variable value into your table.

Maybe that'll help you?

[thejman250]

- a simple solution to this would be to have a function run a loop for every number to see what numbers are actually factors of it.

- Then another function can determine if the factor is a prime number or not.

- Then you can store the numbers that satisfy both of those conditions in an array, and go through it for the largest value.

[Duthomhas]

Arrays are never a simple solution. The simple solution would be do like you said, but if you find a factor, you know to stop looping because the number cannot be prime.

@tcs
Yeah! Someone else recommends pulling out a piece of paper. (About TIME!)

I usually find it easier to just use a text editor and list the variables with an equals sign, then run through my algorithm and update them as I go.

But drawing pictures to help. Good job friend!

:O)

[Neil010]

@Duoas, thank you very much for taking the time to answer my question, and with such detail. It gave me a lot of insight to the problem and I learnt a new (more efficient and rather elegant) way of tackling the problem.

I'm not quite sure what might have made you think that someone gave me the code (maybe because of my style of coding, haha!), but it's just that I made a similar program in Turing where I had to determine the number of prime number in n numbers, and that's what I based that section of the code of.

Once again, thank you very much for the help!

@tcs, thanks for the tip! I do often write down and plan code on paper before typing it out.