#encoding:utf-8
# 快速判定素数,用素数判定素数。比如求1-100之间的素数,
# 先求1-10之间的素数为[2,3,5,7],
# 再用11-100的数%[2,3,5,7],不能被整除的就是素数
# 直接判定一个数是否为素数
def is_prime?(n)
t = 2
while (t <= Math.sqrt(n).to_i)
if (n % t == 0)
return false
end
t = t + 1
end
if n <= 1
return false
end
return true
end
def get_prime(n1,n2)
result = [] # result用于保存begin-end之间的所有素数
temp = [] # 保存2-Math.sqrt(end)之间的所有素数
temp_index = 0
result_index = 0
for i in 2 .. Math.sqrt(n2).to_i
if is_prime?(i)
temp[temp_index] = i
temp_index = temp_index + 1
end
end
temp.each{|i|
if i >= n1
result[result_index] = i
result_index = result_index + 1
end
# print i," "
}
# puts
start = Math.sqrt(n2).to_i
if start > n1
n1 = start
end
for i in n1 .. n2
flag = true
temp.each{|t|
if i % t == 0
flag = false
break
end
}
if flag
result[result_index] = i
result_index = result_index + 1
end
end
return result
end
puts "请输入两个数并按回车键(格式为a b):"
while true
num = gets.split(" ")
n1 = num[0].to_i
n2 = num[1].to_i
result = get_prime(n1,n2)
result.each{|i|
print i," "
}
puts
end
分享到:
相关推荐
革命性素数算法:计算1亿内素数只要1.6秒 算法基本跟之前发的C#版相同(http://download.csdn.net/source/690005内有算法描述),由我的朋友杨力2年前设计,时间复杂O(n)。我对其进行了革命性的数据结构改进,空间...
本篇文章将深入探讨几种经典的素数检测算法,这些算法适用于计算机编程,特别是对于参与ACM竞赛的学生来说,理解并掌握它们是十分有益的。 1. **基础判断法**: 最基础的素数检测方法是遍历从2到n-1的所有整数,...
大范围的素数算法,解决素数算法的问题,当程序需要,为什么非得20个字的描述呢
- 快速生成大素数。 - 减少误判的概率。 - 适用于安全领域的加密算法。 以上内容综合了基础素数生成算法、命令行脚本实现、以及概率性素数测试算法的关键知识,希望能帮助理解素数算法的核心原理及其实际应用。
大素数的生成算法通常用于建立加密系统,如RSA公钥加密算法,其中需要找到两个非常大的质数来生成密钥对。速度很快的大素数生成算法对于提高系统的效率至关重要。 1. **大素数生成算法**: - **米勒-拉宾素性检验...
### Java中的素数算法 #### 一、引言 在计算机科学领域,特别是算法与数据结构的研究中,素数检测是一项基本且重要的任务。本文将详细介绍一个简单的Java程序,该程序能够有效地找出并打印出前500个素数。 #### ...
### AKS素数检测算法(多项式时间内检测) #### 概述 AKS算法是由Manindra Agrawal教授及其两名学生Neeraj Kayal和Nitin Saxena在坎普尔印度理工学院开发的一种用于判断整数是否为素数的新算法。该算法的重要贡献...
基于求逆转换为乘法的思想,利用仿射坐标提出了直接计算椭圆曲线上[7P]的算法,该算法运算量为I 23M 10S,比现有的算法节省了一次求逆运算,同时也给出了直接计算[7kP]的快速算法,该算法比重复计算[k]次[7P]更有效...
### 相邻素数算法详解 #### 一、引言 在算法设计与分析的课程中,有一种较为重要的算法——相邻素数算法。本篇文章将详细介绍该算法的基本概念、实现原理以及具体的步骤演示,帮助读者深入理解并掌握这一算法。 #...
使用拉宾米勒算法流程写的源码,当时也是借鉴别人的,用来学习。有注释,可以帮你理解这个算法
素数的求解算法主要包括素数检测算法和生成素数列表的方法。 1. **基本素性测试算法**: - 最简单的方法是从2到\( \sqrt{n} \)依次检查每个数是否能整除\( n \)。 - 代码示例(C语言): ```c bool IsPrime...
最快求素数的算法,求100000000以下所有素数0.3秒 , 在10000000以下的数中找到664579个素数,耗时53毫秒
快速傅里叶变换算法 快速傅里叶变换(Fast Fourier Transform,FFT)是一种快速算法,用于计算离散傅里叶变换(Discrete Fourier Transform,DFT)。 FFT 是一种分治法的实现,通过将原始问题分解成规模更小的子...
Manindra Agrawal教授和他的两个学生Neeraj Kayal和Nitin Saxena在坎普尔印度技术研究...AKS算法证明了可以应用一个确定的算法在输入规模的多项式时间内决定一个整数是否为素数的问题,而没有使用任何未证明的数学假定
**素数判定:Miller-Rabin算法** 在计算机科学和数论中,素数判定是一个重要的问题,特别是对于大整数。...在需要快速筛选素数的场景,如加密算法或大规模数据处理中,Miller-Rabin算法具有广泛的应用价值。
**米勒-拉宾素数测试算法** 在数学和计算机科学中,判断一个大整数是否为素数是一项基础但重要的任务。米勒-拉宾素数测试算法(MILLER-RABIN Primality Test)是一种概率性算法,用于检测一个正整数是否可能为素数...
RSA算法基于一个十分简单的数论事实:将两个大素数相乘十分容易,但是想要对其乘积进行因式分解却极其困难,因此可以将乘积公开作为加密密钥。RSA算法是第一个能同时用于加密和数字签名的算法,也易于理解和操作。...
在编程和计算机科学领域,素数高效算法是一个关键的研究方向,尤其对于数学、密码学以及高性能计算等应用。本文将详细探讨"逐步修改素数高效算法",旨在为读者提供深入的理解和参考。 首先,素数是大于1且只有1和其...