Chinaunix

标题: [练习] 多少个半质数 [打印本页]

---

作者: rubyish    时间: 2014-02-20 03:15
标题: [练习] 多少个半质数
定义: 半质数
如果一个数恰好是两个质数的乘积（可以相同），则称它为半质数。

前几个半质数是 4, 6, 9, 10, 14, 15, 21, 22, 25, 26.....

问题:

输入两个正整数 x, y ( x < y )，问 x, y 之间有多少个半质数？

---

作者: rubyish    时间: 2014-02-26 01:21

1. #!/usr/bin/ruby -w
   
2. 
   
3. x, y  = print("x, y ") || gets.scan(/\d+/).map(&:to_i)
   
4. y2    = (y / 2).to_i
   
5. prime = (0 .. y2).to_a
   
6. sqrt  = Math.sqrt(y).to_i
   
7. sqrt2 = Math.sqrt(y2).to_i
   
8. count = 0
   
9. prime[0] = prime[1] = nil
   
10. 
    
11. prime.each do |i|
    
12.   next unless i
    
13.   break if i > sqrt2
    
14.   (i ** 2).step(y2, i) {|j| prime[j] = nil }
    
15. end
    
16. 
    
17. prime.compact!
    
18. 
    
19. prime.each_with_index do |p1, i|
    
20.   break if p1 > sqrt
    
21.   prime[i .. -1].each do |p2|
    
22.     sp = p1 * p2
    
23.     sp > y ? break : sp > x && count += 1
    
24.   end
    
25. end
    
26.   
    
27. puts count
    

复制代码

---

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)

Powered by Discuz! X3.2