Go4Expert - Finding Unique Prime Factors with Bitsets

Go4Expert (http://www.go4expert.com/)

- C++ (http://www.go4expert.com/forumdisplay.php?f=100)

- - Finding Unique Prime Factors with Bitsets (http://www.go4expert.com/showthread.php?t=15313)

Finding Unique Prime Factors with Bitsets

Hi

My assignment is to find the unique prime factors of a user inputed number. So for 54, the uniqe prime factors would be 2 and 3. If we display the factors as 2 3 3 3 we get extra credit. I figured out how to do this without manipulating bit by bit (not the extra credit). We were never told if it had to be bit by bit so my question is: is it easy to display these factors using bit manipulation? The reason i ask is if its 10,000 lines or something crazy i doubt my teacher would make us do it. If it is simple and I just can't get my head around it then please tell me so and please provide a starting point.

If you have a way for me to get the extra credit with my current code I would appreciate it cuz i cant figure it out.

My source code is below

Thanks

Code:

#include "stdafx.h"

#include <iostream>

#include <iomanip>

#include <cmath> 

#include <bitset> 



using namespace std;



void getFactors (int n)

{        

        for ( int i = 1 ; i <= n ; i++ )

        {

                int j = i - 1;        

                while ( j > 1 )

                {

                        if ( i % j == 0 )

                                break;

                        else

                                j--;

                }

                if ( j == 1 )

                {

                        if ( n % i == 0 )

                        {                                                                                

                                cout<<i<<"   "; 

                        }

                }        

        }

        cout<<endl;

}



int _tmain(int argc, _TCHAR* argv[])

{

   const int SIZE = 1024;

   int value;

   std::bitset< SIZE > sieve; // create bitset of 1024 bits

   sieve.flip(); // flip all bits in bitset sieve

   sieve.reset( 0 ); // reset first bit (number 0)         

   sieve.reset( 1 ); // reset second bit (number 1)        



   // perform Sieve of Eratosthenes

   int finalBit = sqrt( static_cast< double > ( sieve.size() ) ) + 1;



   // determine all prime numbers from 2 to 1024

   for ( int i = 2; i < finalBit; i++ )

   {

      if ( sieve.test( i ) ) // bit i is on

      {

         for ( int j = 2 * i; j < SIZE; j += i ) 

            sieve.reset( j ); // set bit j off

      } // end if

   } // end for



   cout << "The prime numbers in the range 2 to 1023 are:\n";



   // display prime numbers in range 2-1023

   for ( int k = 2, counter = 1; k < SIZE; k++ )

   {

      if ( sieve.test( k ) ) // bit k is on

      {

         cout << setw( 5 ) << k;



         if ( counter++ % 12 == 0 ) // counter is a multiple of 12

            cout << '\n';

      } // end if          

   } // end for    

   

   cout << endl;



   // get value from user 

   cout << "\nEnter a value from 2 to 1023 (-1 to end): ";

   cin >> value;



   // determine whether user input is prime

   while ( value != -1 ) 

   {

      if ( sieve[ value ] ) // prime number

          {

         cout << value << " is a prime number\n";

          }

      else // not a prime number

          {

                  cout << value << " is not a prime number\n The unique prime factors are: ";

                  getFactors(value);

          }

      

      cout << "\nEnter a value from 2 to 1023 (-1 to end): ";

      cin >> value;

   } // end while



        return 0;

}

Re: Finding Unique Prime Factors with Bitsets

The requirements seem to contradict each other. If you have to find UNIQUE prime factors then why would you get extra credit for displaying duplicates?

If you just have to find all prime factors, unique or not, then the best place to start is to do it yourself on paper. Do you know how to find prime factors of a number? (If not then you're never going to be able to program a computer to do it.)

If you do then do it on paper for a few different numbers, thinking how a computer might do it. The infamous "show your working" is useful here; this is the part that will lead to an algorithm.

What does the code that you've posted do?

Why would you want to use bit manipulation to solve this? Seems counter-intuitive to me to do it that way. Bit manipulation is good for powers of 2, and there's only one prime number that's a power of 2, and that's 2 itself. Bit manipulation can tell you if something is a multiple of 2 - if bit 0 is 0 then it is, but that doesn't solve the whole problem. How can you tell with bit manipulation if something is divisible by 3? 11? 59?

Re: Finding Unique Prime Factors with Bitsets

The program above asks a user for a number. For example, 54 and then if it is prime says so but if it isn't prime tells what the unique prime numbers are which is 2 and 3. That's basically what are assignment was. My question though is: is it overly difficult to do the assignment bit by bit but I think you might have answered my question. So thanks.

Re: Finding Unique Prime Factors with Bitsets

BTW What was the logic of 2 3 3 3

Re: Finding Unique Prime Factors with Bitsets

I have a logic for this one....

Firstly, I develop a program that will search for unique primes of a given no. n, and store them in an array a, and return it.
Secondly, for each aaray element, I store the maximum power of the prime a[i] that divides n in the i'th place of another array b, having the same size of a.
Finally I print the sequence as....

Code:

printf("n=");

for(i=0;i<m;i++)                                /* m is the no. of elements in a (or b) */

    printf("%d^%d.", a[i], b[i]);             /* I use ^ to implement the "to the power" symbol */

Thus the output will be....

Code:

54=2.3^3

I think this will work....cheers everyone... :)