-
Notifications
You must be signed in to change notification settings - Fork 255
/
primes.rb
155 lines (130 loc) · 2.67 KB
/
primes.rb
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
# frozen_string_literal: true
require 'socket'
UPPER_BOUND = 5_000_000
PREFIX = 32_338
class Node
attr_accessor :children, :terminal
def initialize
@children = {}
@terminal = false
end
end
class Sieve
def initialize(limit)
@limit = limit
@prime = Array.new(limit + 1, false)
end
def to_list
result = [2, 3]
(5..@limit).each do |p|
result.push(p) if @prime[p]
end
result
end
def omit_squares
r = 5
while r * r < @limit
if @prime[r]
i = r * r
while i < @limit
@prime[i] = false
i += r * r
end
end
r += 1
end
self
end
def step1(x, y)
n = (4 * x * x) + (y * y)
@prime[n] = !@prime[n] if n <= @limit && (n % 12 == 1 || n % 12 == 5)
end
def step2(x, y)
n = (3 * x * x) + (y * y)
@prime[n] = !@prime[n] if n <= @limit && n % 12 == 7
end
def step3(x, y)
n = (3 * x * x) - (y * y)
@prime[n] = !@prime[n] if x > y && n <= @limit && n % 12 == 11
end
def loop_y(x)
y = 1
while y * y < @limit
step1(x, y)
step2(x, y)
step3(x, y)
y += 1
end
end
def loop_x
x = 1
while x * x < @limit
loop_y(x)
x += 1
end
end
def calc
loop_x
omit_squares
end
end
def generate_trie(l)
root = Node.new
l.each do |el|
head = root
el.to_s.each_char do |ch|
head.children[ch] = Node.new unless head.children[ch]
head = head.children[ch]
end
head.terminal = true
end
root
end
def find(upper_bound, prefix)
primes = Sieve.new(upper_bound).calc
str_prefix = prefix.to_s
head = generate_trie(primes.to_list)
str_prefix.each_char do |ch|
head = head.children[ch]
return nil if head.nil?
end
queue = [[head, str_prefix]]
result = []
until queue.empty?
(top, prefix) = queue.pop
result.push(prefix.to_i) if top.terminal
top.children.each { |ch, v| queue.insert(0, [v, prefix + ch]) }
end
result.sort!
result
end
def notify(msg)
Socket.tcp('localhost', 9001) { |s| s.puts msg }
rescue SystemCallError
# standalone usage
end
def verify
left = [2, 23, 29]
right = find(100, 2)
return unless left != right
warn "#{left} != #{right}"
exit(1)
end
if __FILE__ == $PROGRAM_NAME
verify
engine = RUBY_ENGINE
if engine == 'truffleruby'
desc = RUBY_DESCRIPTION
if desc.include?('Native')
engine = 'Ruby/truffleruby'
elsif desc.include?('JVM')
engine = 'Ruby/truffleruby (JVM)'
end
elsif engine == 'ruby' && RubyVM::RJIT.enabled?
engine = 'Ruby (--jit)'
end
notify("#{engine}\t#{Process.pid}")
results = find(UPPER_BOUND, PREFIX)
notify('stop')
puts results.inspect
end