# Finding Unique Prime Factors with Bitsets

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

1. ### thekevin07New Member

Joined:
Sep 13, 2008
Messages:
29
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. ### xpi0t0sMentor

Joined:
Aug 6, 2004
Messages:
3,009
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. ### thekevin07New Member

Joined:
Sep 13, 2008
Messages:
29
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. ### coderzoneSuper Moderator

Joined:
Jul 25, 2004
Messages:
736
37
Trophy Points:
28
BTW What was the logic of 2 3 3 3

5. ### back from retirementNew Member

Joined:
Nov 9, 2008
Messages:
72
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... 