Solved

SEMANTIC ERROR  with while loop in C program

Posted on 2006-07-06
4
1,368 Views
Last Modified: 2012-08-14
I'm using a while loop to calculate prime factors. I'm getting the prime factors, but I'm getting TWO sets of each one. So, for 100 (primes should be just 2 and 5, I'm getting 2 2 5 5. Could someone please take a look at my code (especially my while loop) and suggest where my error might be? Any other general suggestions on how to improve what I've written would also be appreciated.

------------------------------------MY CODE-------------------------------------------------------

// prime factorizarion.

#include <stdio.h>

// isPrime function
// return 1 if number prime
int isPrime(int n)
{
int i = 2;
while ( i <= n/2 )
{      if ( (n % i) == 0 )
             //this is not a prime
             return 0;
       i++;
}
// this is a prime
return 1;
}



// prime factor a number
int main()
{
    int prime; // prime divider
    int num; // number to find primes factors of

    // get number
    printf("Enter a number greater than 1: ");
    scanf("%d",&num);

   while(num > 1)
   {
    prime = 2; // start with lowest prime

    // To prime factor a number, begin dividing by the smallest possible prime
    // and continue until the quotient is a prime number.
    while(!isPrime(num))
    {
          // test if num is prime
          if((num % prime)==0)
          {
              printf("%d ",prime);  // print out factor
              num = num / prime;
          }

          // find next prime
          else
          {
              prime++;

              while(!isPrime(prime))
              {
                  prime++;
              }
          }

    }

    // print out last factor
   printf("%d\n",num);

       // get next  number
    printf("Enter a number greater than 1: ");
    scanf("%d",&num);
   }

     
   printf("\n");

return 1;
}
0
Comment
Question by:computerese
  • 3
4 Comments
 
LVL 5

Expert Comment

by:bastibartel
ID: 17052534
Hi there,

Turn this:
// test if num is prime
          if((num % prime)==0)
          {
              printf("%d ",prime);  // print out factor
              num = num / prime;
          }


Into this  (use a while loop to divide be the prime as OFTEN as possible)

// test if num is prime
          while((num % prime)==0)
          {
              printf("%d ",prime);  // print out factor
              num = num / prime;
          }
0
 
LVL 5

Assisted Solution

by:bastibartel
bastibartel earned 250 total points
ID: 17052550
Sorry, this still printed out the prime several times ;-)

if((num % prime)==0)
{
      printf("%d ",prime);  // print out factor only once
      while((num % prime)==0)  
            num = num / prime;     // but divide as often as possible
}
         

0
 
LVL 16

Accepted Solution

by:
PaulCaswell earned 250 total points
ID: 17052567
Hi computerese,

Your code, when presented with 100 will go through the following steps:

Is 2 a prime factor of 100? Yes! Print '2' and set number to 50.
Is 2 a prime factor of 50? Yes! Print '2' and set number to 25.
Is 2 a prime factor of 25? No!
Is 3 a prime factor of 25? No!
Is 5 a prime factor of 25? Yes! Print '5' and set number to 5.
Is 2 a prime factor of 5? No!
Is 3 a prime factor of 5? No!
Is 5 a prime factor of 5? Yes! Print '5' and set number to 1.
Finished.

So the correct prime fators of 100 ARE 2,2,5,5. What did you expect?

You may like to change this code:

          if((num % prime)==0)
          {
              printf("%d ",prime);  // print out factor
              while ( (num % prime) == 0 ) num = num / prime;
          }


Paul
0
 
LVL 5

Expert Comment

by:bastibartel
ID: 17056438
:-)
0

Featured Post

Highfive + Dolby Voice = No More Audio Complaints!

Poor audio quality is one of the top reasons people don’t use video conferencing. Get the crispest, clearest audio powered by Dolby Voice in every meeting. Highfive and Dolby Voice deliver the best video conferencing and audio experience for every meeting and every room.

Join & Write a Comment

Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see so…
The goal of this video is to provide viewers with basic examples to understand and use conditional statements in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use switch statements in the C programming language.

762 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

21 Experts available now in Live!

Get 1:1 Help Now