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?
What's allowed:
bit-manipulations which take 1 argument are allow. This includes functions like
not
but notxor
.if
s and loops are allowed but bits innum
will be used for the flag. (no usingif num > 2
)num
is the only variable/constant allowed to be declared. We cannot(num)
(flip every bits innum
) but notnum - 2
(2
is another var/const).- Operating on bits only in
num
like summing all the bits (bit_sum(20) = bit_sum(b1010) = 2
because there are 21
s)
Bonus if the operation can quickly be done by hand like the given examples for base 10.