Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C++ (http://www.go4expert.com/forums/cpp/)
-   -   Finding Unique Prime Factors with Bitsets (http://www.go4expert.com/forums/finding-unique-prime-factors-bitsets-t15313/)

thekevin07 2Dec2008 04:13

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;
}


xpi0t0s 2Dec2008 14:00

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?

thekevin07 3Dec2008 00:37

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.

coderzone 3Dec2008 10:15

Re: Finding Unique Prime Factors with Bitsets
 
BTW What was the logic of 2 3 3 3

back from retirement 3Dec2008 11:41

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... :)


All times are GMT +5.5. The time now is 23:02.