Prime Factorization (and other things)

Help
1

Is there a quick way/algorithm to find the prime factorization of a positive integer in gimkit?

8 Likes
2

Let’s see. Usually I would just divide by 2, 3, 5, 7, or 9, depending on the number.

Maybe if it’s an even number, we could divide by two first? Let’s start from there.
We would need a trigger loop though, and bracastbroadcast to stop the loop and move on when the number contains a . or == 1

Also shouldn’t this be in Devices research because its research?

Edit: Ouch, I spelled broadcast wrong >_<

3 Likes
3

You would need to simulate the algorithm yourself.

I don’t know, but I pretty sure you can’t.

3 Likes
4

Turns out I don’t need prime factorization, but I do need the GCD function. I’m going to go search if that’s in gimkit…

4 Likes
5

Still requires a loop though

2 Likes
6

Turns out that these blocks exist… which might be really useful:

image
image230×284 11.1 KB

7 Likes
7

For GCD(a,b) and a ≠ b:

import math

while m != 0:
  if a > b:
    lm = m
    m = math.mod(a, b)
    a = b
    b = m
  else:
    lm = m
    m = math.mod(b, a)
    b = a
    a = m

print(f"GCD of a and b is {lm}")

(This was in python, hopefully it’s easy to convert bc python is so straightforward)
However, this requires a loop, which we DON’T have in the Blockly interface but we DO have with single trigger loop
@drawfine

1 Like
8

Wait what device is this? I want to recreate it.

9

Oh I meant the code is written in python,it’s easy to convert imo bc of how everything types is exactly as it says.if I type a = b then a equals b.

If you’re talking abt putting it on which device, I’d say trigger cause trigger can loop. Don’t forget three properties:one for a, b, and the result

10

Ok correct me if I’m wrong. But what is lm, like the result?

11

Outline Idea - first ten numbers
Ignore the first number (1).
2-3: If the # is prime (not 1) : add it to the divisors list.
4: If the number is not prime, use the first divisor and print this divisor out. 4/2 = 2. This is our next number. If it is whole, repeat until number is one. 2/2 = 1. As number is one, final output. Output would be 2 2. If the output repeats the same number, convert this to exponential notation. 2 ^ 2
5 is prime
6: The number is not prime. Divisor: 2 → 3 . 3/2 is not whole, 3/3 is whole. The number is now 1 so our printed values are 3 2. Since there are only one instance of each factors do not use exponents
7 is prime
8: not prime. divisor is 8/2 → 4 , 4/2 → 2, 2/2 → 1. As it is one, printed value is 2 2 2 . Convert to exponent notation : 2 ^ 3
9: not prime. divisor is 9/2 is not whole. 9/3 is whole so 9/3=3. Repeat: 3/2 is not whole, 3/3 =1. Our printed factors are 3 3 so exponent notation is 3^2
10: not prime. divisor is 10/2=5, but 5/2 and 5/3 are not whole numbers. 5/5=1. Since it is now 1, output is 2 5. Since there are only one instance of each factors do not use exponents

Summary (steps):

  1. skip 1
  2. is number prime, if so add to divisors
  3. is number not prime? divide by divisor and print out divisor if output is whole
  4. after getting a whole , divide again and print again until number is 1.
  5. exponential notation by # of factors (not sure how this would work)
2 Likes
12

a variable. i just named it lm for last mod
and yes the output

1 Like
14

That’s the Euclidean Algorithm, right? I’m pretty sure it is possible to replicate the mod function in gimkit, so this is possible to implement.

3 Likes
15

Both lol

Yep and yep. Just gotta find that one modulus guide…