9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
# File 'ext/factorization/factorization.c', line 9
static VALUE
factorize_pq(VALUE self, VALUE pq_bytes)
{
Check_Type(pq_bytes, T_STRING);
long pq_len = RSTRING_LEN(pq_bytes);
unsigned char *pq_ptr = (unsigned char *)RSTRING_PTR(pq_bytes);
uint64_t n = 0;
for (long i = 0; i < pq_len; i++) {
n = (n << 8) | pq_ptr[i];
}
if (n <= 3) {
rb_raise(rb_eArgError, "Number must be > 3");
}
if (n % 2 == 0) {
VALUE result = rb_ary_new2(2);
rb_ary_push(result, ULL2NUM(2));
rb_ary_push(result, ULL2NUM(n / 2));
return result;
}
uint64_t limit = (uint64_t)sqrt((double)n) + 1;
for (uint64_t i = 3; i < limit; i += 2) {
if (n % i == 0) {
uint64_t p = i;
uint64_t q = n / i;
if (p > q) {
uint64_t tmp = p;
p = q;
q = tmp;
}
VALUE result = rb_ary_new2(2);
rb_ary_push(result, ULL2NUM(p));
rb_ary_push(result, ULL2NUM(q));
return result;
}
}
rb_raise(rb_eRuntimeError, "No non-trivial factors found (n might be prime)");
}
|