-
Notifications
You must be signed in to change notification settings - Fork 6
/
800 Hybrid Integers.pl
65 lines (46 loc) · 1.17 KB
/
800 Hybrid Integers.pl
1
2
3
4
5
6
7
8
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
54
55
56
57
58
59
60
61
62
63
64
65
#!/usr/bin/perl
# Author: Trizen
# Date: 03 November 2022
# https://github.com/trizen
# Hybrid Integers
# https://projecteuler.net/problem=800
# Runtime: 2 seconds.
use 5.020;
use warnings;
use ntheory qw(:all);
use experimental qw(signatures);
sub bsearch_le ($left, $right, $callback) {
my ($mid, $cmp);
for (; ;) {
$mid = int(($left + $right) / 2);
$cmp = $callback->($mid) || return $mid;
if ($cmp < 0) {
$left = $mid + 1;
$left > $right and last;
}
else {
$right = $mid - 1;
if ($left > $right) {
$mid -= 1;
last;
}
}
}
return $mid;
}
sub C ($n, $e) {
my $limit = log($n) * $e;
my $count = 0;
for (my $p = 2 ; ; $p = next_prime($p)) {
my $p_log = log($p);
my $k = bsearch_le($p + 1, int($limit / $p_log), sub ($q) {
$p_log * $q + log($q) * $p <=> $limit;
});
$count += (prime_count($p + 1, $k) || last);
}
return $count;
}
say C(800, 1); #=> 2
say C(163, 165); #=> 1000
say C(800, 800); #=> 10790
say C(800800, 800800);