https://projecteuler.net/problem=3 https://projecteuler.net/problem=3
The problem is as follows:
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
I am trying to solve it as follows:
package main import ( "fmt" ) func primeset(n uint64) uint64 { primes := uint64(0) for p:= uint64(2);p <= n;p++ { if((primes & (1 << p)) == 0){ fmt.Println("Current prime",p) for j:=uint64(2)*p;j <=n;j=j+p { fmt.Println("Current num:",j) primes |= (1 << j) fmt.Println("Bitset value is:",primes) } } } return primes } func main() { n := uint64(100) primes := primeset(n) fmt.Println("Primes is",primes) j := n for j >= 2 { s := primes & (1 << uint64(j)) if((s == 0) && ((n % j) == 0)){ fmt.Println("Largest factor",j) return } else { j-- } } }
In the function primeset , I start with an unsigned int called primes with an initial value of 0 and then I left shift by a number(which is a composite) and set that bit of primes to 1.
The idea is that I simply check the 4th bit of primes to see if it has been set. If the bit is set, its not a prime.
For small numbers the code seems to work but when I started testing it for numbers such as 100, all of a sudden things were rather bizzare.
I noticed that the bit shifting is not working while trying to set it for the 62nd bit onwards. The following trace can demonstrate the situation:
Current num: 48 Bitset value is: 375299968947536 Current num: 50 Bitset value is: 1501199875790160 Current num: 52 Bitset value is: 6004799503160656 Current num: 54 Bitset value is: 24019198012642640 Current num: 56 Bitset value is: 96076792050570576 Current num: 58 Bitset value is: 384307168202282320 Current num: 60 Bitset value is: 1537228672809129296 Current num: 62 Bitset value is: 6148914691236517200 Current num: 64 Bitset value is: 6148914691236517200 Current num: 66 Bitset value is: 6148914691236517200 Current num: 68 Bitset value is: 6148914691236517200 Current num: 70 Bitset value is: 6148914691236517200 Current num: 72 Bitset value is: 6148914691236517200 Current num: 74 Bitset value is: 6148914691236517200 Current num: 76 Bitset value is: 6148914691236517200 Current num: 78 Bitset value is: 6148914691236517200 Current num: 80 Bitset value is: 6148914691236517200 Current num: 82 Bitset value is: 6148914691236517200 Current num: 84 Bitset value is: 6148914691236517200 Current num: 86 Bitset value is: 6148914691236517200
Can somebody point out what might be off with the way I am performing my bit operations?
Thanks