对于库,我需要将第一个素数存储到极限L.此集合必须具有O(1)查找时间(以检查数字是否为素数)并且必须很容易,给定数字,找到下一个素数(假设它小于L).
鉴于L是固定的,生成清单的Eratostene筛子很好.现在,我使用一个打包的布尔数组来存储列表,该列表仅包含3到L(含)之间的奇数的条目.这需要(L-2)/ 2位内存.我希望能够在不使用更多内存的情况下静态增加L.
是否存在使用具有相似属性的较少内存的数据结构？或者至少具有恒定的查找时间？(然后可以枚举奇数,直到我们得到一个素数)
(我在其中编写的语言是因子,但这个问题在内置或易于编程的打包位数组的任何语言中都是相同的)
我们在工作中有点乐趣.这一切都始于其中一个设置Hackintosh的人,我们想知道它是否比我们拥有的(几乎)相同规格的Windows Box更快.所以我们决定为它写一点测试.只是一个简单的Prime数字计算器.它是用Java编写的,它告诉我们计算前n个Prime数字所需的时间.
下面的优化版本 - 现在需要~6.6秒
public class Primes {
public static void main(String[] args) {
int topPrime = 150000;
int current = 2;
int count = 0;
int lastPrime = 2;
long start = System.currentTimeMillis();
while (count < topPrime) {
boolean prime = true;
int top = (int)Math.sqrt(current) + 1;
for (int i = 2; i < top; i++) {
if (current % i == 0) {
prime = false;
break;
}
}
if (prime) {
count++;
lastPrime = current; …是否有一个函数可以返回第n个素数的近似值？我认为这将类似于近似反向素数计数功能.例如,如果我给这个函数25它将返回一个大约100的数字,或者如果我给这个函数1000它将返回一个大约8000的数字.我不在乎返回的数字是否是素数,但我确实想要它要快(所以不产生前n个素数以返回第n个.)
我想这样我可以使用筛子(Eratosthenes或Atkin)生成前n个素数.因此,理想情况下,n th 的近似值永远不会低估实际第n个素数的值.
(更新:请参阅我的答案,找到找到第n个素数上限的好方法.)
我正在练习过去的基础java考试的考试试卷,我发现很难做一个for循环工作来测试一个数字是否是素数.我不想通过为更大的数字添加效率测量来使其复杂化,这只是至少适用于2位数字的东西.
目前,即使n是素数,它总是返回false.
我认为我的问题是我在for循环本身出错了,在哪里放"return true".并且"返回虚假;"......我确信这是我犯的一个非常基本的错误......
public boolean isPrime(int n) {
int i;
for (i = 2; i <= n; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
我无法在stackoverflow上找到其他帮助的原因是因为类似的问题要求更复杂的实现以获得更有效的方法.
我是编程世界的新手.我只是在python中编写这段代码来生成N个素数.用户应输入N的值,即打印出的素数总数.我写了这段代码,但它没有抛出所需的输出.相反,它打印素数直到第N个数字.例如:用户输入N = 7的值.所需输出:2,3,5,7,11,13,19实际输出:2,3,5,7
好心提醒.
i=1
x = int(input("Enter the number:"))
for k in range (1, (x+1), 1):
c=0
for j in range (1, (i+1), 1):
a = i%j
if (a==0):
c = c+1
if (c==2):
print (i)
else:
k = k-1
i=i+1
只想要一些关于我的素数发生器的反馈.例如,它是否正常,它是否用于很多资源等.它不使用库,它相当简单,它反映了我目前的编程技巧状态,所以不要因为我想学习而退缩.
def prime_gen(n):
primes = [2]
a = 2
while a < n:
counter = 0
for i in primes:
if a % i == 0:
counter += 1
if counter == 0:
primes.append(a)
else:
counter = 0
a = a + 1
print primes
首先 - 我在这个论坛上检查了很多,但我找不到足够快的东西.我尝试创建一个函数,返回指定范围内的素数.例如,我使用Eratosthenes的筛子完成了这个功能(在C#中).我也试过阿特金的筛子但是Eratosthenes的跑得更快(在我的实施中):
public static void SetPrimesSieve(int Range)
{
Primes = new List<uint>();
Primes.Add(2);
int Half = (Range - 1) >> 1;
BitArray Nums = new BitArray(Half, false);
int Sqrt = (int)Math.Sqrt(Range);
for (int i = 3, j; i <= Sqrt; )
{
for (j = ((i * i) >> 1) - 1; j < Half; j += i)
Nums[j] = true;
do
i += 2;
while (i <= Sqrt && Nums[(i >> 1) - 1]);
}
for …我知道在所有类型的.NET字典和哈希表中都有一个用于:
internal static class HashHelpers
我在闲暇时间玩Euler项目,而且我需要做一些重构.我已经实施了Miller-Rabin以及一些筛子.我之前听说过,对于小数字来说,筛子实际上更快,就像几百万以下一样.有没有人有这方面的信息？谷歌不是很有帮助.
在我对素数的追求中,我已经问过这样一个问题:无法创建巨大的数组,这些数组导致我基于数组字典创建我自己的假数组类...:private Dictionary<int, Array> arrays = new Dictionary<int, Array>();
我可以10 000 000 000使用下面的代码知道创建很多bool(如)的伪数组:
public class CustomArray
{
private Dictionary<int, Array> arrays = new Dictionary<int, Array>();
public CustomArray(ulong lenght)
{
int i = 0;
while (lenght > 0x7FFFFFC7)
{
lenght -= 0x7FFFFFC7;
arrays[i] = new bool[0x7FFFFFC7];
i++;
}
arrays[i] = new bool[lenght];
}
}
但是一旦我要求CustomArray 100 000 000 000元素,它就崩溃了.它适用于25次首次迭代(我的Dictionary包含25个0x7FFFFFC7元素的数组),但随后它会因OutOfMemory异常而崩溃.
剩下的,我有16GB内存,VS2013,程序是用64位编译的,我启用了gcAllowVeryLargeObjects选项,我在任务管理器中看不到任何内存峰值.
我怎样才能避免这个错误？