"A composite is a number containing at least two prime factors. For example, 15 = 3 × 5; 9 = 3 × 3; 12 = 2 × 2 × 3.
There are ten composites below thirty containing precisely two, not necessarily distinct, prime factors: 4, 6, 9, 10, 14, 15, 21, 22, 25, 26.
How many composite integers, n < 10^[sup]8[/sup], have precisely two, not necessarily distinct, prime factors?
"
Jakoś nie bardzo to jest dobrze, ale może ktoś wpadnie jak to poprawić
[code=ruby]class Integer
Miller-Rabin Test (Prime Test)
See, http://www.cs.albany.edu/~berg/csi445/Assignments/pa4.html
def bitarray(n)
b=Array::new
i=0
v=n
while v > 0
b[i] = (0x1 & v)
v = v/2
i = i + 1
end
return b
end
def miller_rabin(n,s)
b=bitarray(n-1)
i=b.size
j =1
while j <= s
a = 1 + (rand(n-2).to_i)
if witness(a,n,i,b) == true
return false
end
j+=1
end
return true
end
def witness(a,n,i,b)
d=1
x=0
while i > 0
x = d
d = (d**2) % n
if ( (d == 1) && (x != 1) && (x != (n-1)) )
return true
end
if ( b[i-1] == 1 )
d = (d * a ) % n
end
i -= 1
end
if ( d != 1)
return true
end
return false
end
#def prime?
def is_prime?
a = self
return miller_rabin(a,30)
end
end
def divisions(x)
(2…x).inject([]) do |t, d|
t += ((x%d == 0 && d.is_prime?) ? [d] : [])
end
end
ile = 0
3.upto(10**8) do |x|
td = divisions(x)
if td.count == 2 then
#p “#{x} #{td}”
ile+=1
end
end
p ile[/code]