I am trying to solve project euler problem 3 in golang:
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