I've read about some methods of prime factorization like here and here. However, I'm wondering: what can we do in prime factorization with just some bit manipulation and without other variables/constants?
In base 10, we can get some hints about the factors of an integer just be checking the digits:
- digit's place is even --> int is even
- digit's place is 0 of 5 --> int is divisible by 5
- sum_of_digit % 3 = int % 3
- sum_of_digit % 9 = int % 9
Given an integer
num as a bit array, how can we check for
num's primality and guess or extract its prime factors just by looking at its bits like we do with digits in base 10?
There are 5 0's --> (num % (2^5)) = 0 / \ / \ | | 1010101110100000 | | ^ | | | last bit is 0 --> num is even | | v may be these 3 bits can give some information?
bit-manipulations which take 1 argument are allow. This includes functions like
ifs and loops are allowed but bits in
numwill be used for the flag. (no using
if num > 2)
numis the only variable/constant allowed to be declared. We can
not(num)(flip every bits in
num) but not
num - 2(
2is another var/const).
- Operating on bits only in
numlike summing all the bits (
bit_sum(20) = bit_sum(b1010) = 2because there are 2
Bonus if the operation can quickly be done by hand like the given examples for base 10.