Finding Unique Prime Factors with Bitsets

Discussion in 'C++' started by thekevin07, Dec 1, 2008.

  1. thekevin07

    thekevin07 New Member

    Joined:
    Sep 13, 2008
    Messages:
    29
    Likes Received:
    0
    Trophy Points:
    0
    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;
    }
     
  2. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,009
    Likes Received:
    203
    Trophy Points:
    63
    Occupation:
    Senior Support Engineer
    Location:
    England
    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?
     
  3. thekevin07

    thekevin07 New Member

    Joined:
    Sep 13, 2008
    Messages:
    29
    Likes Received:
    0
    Trophy Points:
    0
    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.
     
  4. coderzone

    coderzone Super Moderator

    Joined:
    Jul 25, 2004
    Messages:
    736
    Likes Received:
    38
    Trophy Points:
    28
    BTW What was the logic of 2 3 3 3
     
  5. back from retirement

    back from retirement New Member

    Joined:
    Nov 9, 2008
    Messages:
    72
    Likes Received:
    1
    Trophy Points:
    0
    Occupation:
    Student, UG 1st Yr., Jadavpur University
    Location:
    Uttarpara, West Bengal, India
    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 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... :)
     

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice