If this gets a post ID of 32768, we advance!

[TonyBrown148]

tbgs write my college assignment

1. find all divisors of n

Code Select Expand

#include
int n;
int main()
{
   scanf("%d", &n);
   int i;
   for (i = 1; i <= n; i++) {
      if (n % i == 0) {
         printf("%d\n", i);
      }
   }
   return 0;
}


[red herring]

tbgs write my college assignment

1. find all divisors of n

Code Select Expand

#include
int n;
int main()
{
   scanf("%d", &n);
   int i;
   for (i = 1; i <= n; i++) {
      if (n % i == 0) {
         printf("%d\n", i);
      }
   }
   return 0;
}


optimize this by only iterating from 1 to sqrt(n)

[PkmnQ]

tbgs write my college assignment

1. find all divisors of n

Code Select Expand

#include
int n;
int main()
{
   scanf("%d", &n);
   int i;
   for (i = 1; i <= n; i++) {
      if (n % i == 0) {
         printf("%d\n", i);
      }
   }
   return 0;
}


optimize this by only iterating from 1 to sqrt(n)

then n = 12 wouldn't be able to print 6, unless you stored them in a list

[Gilbert189]

fast food
but the signal blipped and i heard fart food instead

[Byron_Inc_TBG]

hypotenuse

[red herring]

tbgs write my college assignment

1. find all divisors of n

Code Select Expand

#include
int n;
int main()
{
   scanf("%d", &n);
   int i;
   for (i = 1; i <= n; i++) {
      if (n % i == 0) {
         printf("%d\n", i);
      }
   }
   return 0;
}


optimize this by only iterating from 1 to sqrt(n)

then n = 12 wouldn't be able to print 6, unless you stored them in a list

You can just divide n with the i to get the other factor, no?
so

i = 1 -> factors 12 (n/i) and 1 (i)
i = 2 -> factors 6 (n/i) and 2 (i)
i = 3 -> factors 4 (n/i) and 3 (i)
at that point you stop since sqrt(12) = 3 in the integer world

[PkmnQ]

optimize this by only iterating from 1 to sqrt(n)

then n = 12 wouldn't be able to print 6, unless you stored them in a list

You can just divide n with the i to get the other factor, no?
so

i = 1 -> factors 12 (n/i) and 1 (i)
i = 2 -> factors 6 (n/i) and 2 (i)
i = 3 -> factors 4 (n/i) and 3 (i)
at that point you stop since sqrt(12) = 3 in the integer world

don't they need to be printed in order?

[Byron_Inc_TBG]

Still visible

[red herring]

then n = 12 wouldn't be able to print 6, unless you stored them in a list

You can just divide n with the i to get the other factor, no?
so

i = 1 -> factors 12 (n/i) and 1 (i)
i = 2 -> factors 6 (n/i) and 2 (i)
i = 3 -> factors 4 (n/i) and 3 (i)
at that point you stop since sqrt(12) = 3 in the integer world

don't they need to be printed in order?

then yeah, i suppose you need a list to do that

if you interweave the factors i don't think you need to sort

[1, 12, 2, 6, 3, 4]
print elements 0, 2, 4, then go backwards and print 5, 3, 1

knowing that the array is going to have at most 2*sqrt(n) elements, does that mean the algorithm is O(sqrt(n))?

[TonyBrown148]

optimize this by only iterating from 1 to sqrt(n)

nah i will simply skip all the intermediate steps and use pollard rho

[PkmnQ]

nah i will simply skip all the intermediate steps and use pollard rho

well that's new

[TonyBrown148]

miller rabin using first 5 primes is enough for all unsigned ints.

[Byron_Inc_TBG]

stat

[solitaire]

i just beat a sixth no gun run of ngon

2nd no gun run with all undefined

[TonyBrown148]

Code Select Expand

from itertools import count
from math import gcd
from random import randrange


def quickPow(b, n, mod):
    res = 1
    while n > 0:
        if n % 2 == 0:
            res = res * b % mod
        b = b * b % mod
        n //= 2
    return res


def millerRabin(n):
    if n < 3 or n % 2 == 0:
        return n == 2
    u, t = n - 1, 0
    while u % 2 == 0:
        u //= 2
        t += 1
    for _ in range(8):
        a = randrange(2, n)
        x = quickPow(a, u, n)
        if x == 1:
            continue
        for _ in range(t):
            x = x * x % n
            if x == n - 1:
                break
        else:
            return False
    return True


def pollardRho(n):
    x = randrange(n)
    y = x
    k = 2
    for i in count(1):
        x = (x * x - 1) % n
        d = gcd(y - x, n)
        if d != 1 and d != n:
            return d
        if i == k:
            y = x
            k += i


def factor(n):
    if n < 2:
        return ()
    if millerRabin(n):
        return (n,)
    p = pollardRho(n)
    a = 0
    while n % p == 0:
        n //= p
        a += 1
    return factor(p) * a + factor(n)



[solitaire]

n-gon no gun tip: don't use pilot wave. ever. because you can't fight almost every boss.

[PkmnQ]

n-gon speedrunning tip: crouch at exit

[Byron_Inc_TBG]

k,o

[TwilightSeleneMisty]

we don't talk about bruno no no (word) no

[Byron_Inc_TBG]

e

[TwilightSeleneMisty]

[user=KAWAIICORNS10]test[/user]

[Byron_Inc_TBG]

kp[

[red herring]

Code Select Expand

from itertools import count
from math import gcd
from random import randrange


def quickPow(b, n, mod):
    res = 1
    while n > 0:
        if n % 2 == 0:
            res = res * b % mod
        b = b * b % mod
        n //= 2
    return res


def millerRabin(n):
    if n < 3 or n % 2 == 0:
        return n == 2
    u, t = n - 1, 0
    while u % 2 == 0:
        u //= 2
        t += 1
    for _ in range(8):
        a = randrange(2, n)
        x = quickPow(a, u, n)
        if x == 1:
            continue
        for _ in range(t):
            x = x * x % n
            if x == n - 1:
                break
        else:
            return False
    return True


def pollardRho(n):
    x = randrange(n)
    y = x
    k = 2
    for i in count(1):
        x = (x * x - 1) % n
        d = gcd(y - x, n)
        if d != 1 and d != n:
            return d
        if i == k:
            y = x
            k += i


def factor(n):
    if n < 2:
        return ()
    if millerRabin(n):
        return (n,)
    p = pollardRho(n)
    a = 0
    while n % p == 0:
        n //= p
        a += 1
    return factor(p) * a + factor(n)



I recognize that quick power algorithm, however, I know it in the matrix implementation

Code Select Expand

def mul(a, b, m):
    c00 = a[0][0] * b[0][0] + a[0][1] * b[1][0]
    c01 = a[0][0] * b[0][1] + a[0][1] * b[1][1]
    c10 = a[1][0] * b[0][0] + a[1][1] * b[1][0]
    c11 = a[1][0] * b[0][1] + a[1][1] * b[1][1]
    return [[c00 % m, c01 % m], [c10 % m, c11 % m]]

def bpow(b, e, m):
    r = [[1,0],[0,1]]
    while e:
        if e & 1:
            r = mul(r, b, m)
        b = mul(b, b, m)
        e = e >> 1
    return r

I saw this in a seminar and the lecturer also made a C version, unfortunately I forgot to write that one down


Edit: looks like I did write down the integer version

Code Select Expand

// quick power but with bitwise ops
int bpow(int x, int n)
{
    int xn = 1;
    for (; n; n >>= 1)
    {
        // check if n is even or odd by checking last bit (n & 1)
        if (n & 1) xn *= x;
        x *= x;
    }

    return xn;
}

So i think I can make this in C, shouldn't be too difficult tbh

[TonyBrown148]

So i think I can make this in C, shouldn't be too difficult tbh

remember modulo and be careful about integer overflow

[red herring]

So i think I can make this in C, shouldn't be too difficult tbh

remember modulo and be careful about integer overflow

Yeah, we used long long int + modulo for most of the seminar, this one was an exception (which I believe did get fixed)