我正在编写一个带有一些素数相关方法的小库.因为我已经完成了基础工作(也就是工作方法),现在我正在寻找一些优化.当然,互联网是一个很好的地方.然而,我偶然发现了一个四舍五入的问题,我想知道如何解决这个问题.
在循环中,我用它来测试一个数字,因为它的搜索效率更高,搜索直到sqrt(n)而不是n/2甚至n - 1.但由于舍入问题,一些数字会被跳过,因此会跳过一些素数!例如,第10000个素数应为:104729,但"优化"版本最终为:103811.
一些代码(我知道,它可以进行更多优化,但我一次只能处理一件事):
/// <summary>
/// Method for testing the primality of a number e.g.: return IsPrime(29);
/// History:
/// 1. Initial version, most basic form of testing: m smaller then n -1
/// 2. Implemented m smaller then sqrt(n), optimization due to prime factoring
/// </summary>
/// <param name="test">Number to be tested on primality</param>
/// <returns>True if the number is prime, false otherwise</returns>
public static bool IsPrime(int test)
{
// 0 and 1 are not prime numbers …给定大N,我需要遍历所有phi(k),使得1 <k <N很快.由于N的值约为10 12,因此重要的是存储器复杂度为sub O(n).
可能吗？如果是这样,怎么样？
我正在努力地插入一些检查可分性的代码(是的,这是生成素数),我想知道如果条件满足一次就停止for ...循环.像这样的代码:
$delete = array();
foreach ( $testarray as $v ) {
for ( $b = 2; $b < $v; $b++ ) {
if ( $v % $b == 0 ) {
$delete []= $v;
}
}
所以$testarray是整数1-100,并且$delete数组将被过滤掉$testarray.目前,多次添加12个数字,$delete因为它可以被2,3,4和6整除.当条件匹配一次时,如何通过跳过来节省计算机的时间？
有没有很好的算法可以找到给定real数字的最接近的素数？我只需要在前100个素数内搜索.
目前,我有一堆素数存储在一个数组中,我一次检查一个数字(O(n)？).
是否有一种直接的方法只使用按位运算从2的幂提取指数？
编辑:虽然这个问题最初是关于按位操作的,但如果你想知道" 在Python中给出Y = 2 X时找到X的最快方法是什么,这个线程也很好读"**
我目前试图优化的例程(拉宾-米勒素性测试),以降低一个偶数 N的形式2**s * d.我可以得到这个2**s部分:
two_power_s = N & -N
但我找不到用逐位运算来提取" s " 的方法.我目前正在测试的解决方法没有太多满足(它们都非常慢)是:
我正在使用python,但我认为这个问题的答案应该是语言无关的.
此c ++代码打印出以下素数: 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97.
但我认为这不是我的书想要写的方式.它提到了一些关于数字的平方根的东西.所以我确实尝试改变我的第二个循环,for (int j=2; j<sqrt(i); j++)但它没有给我我需要的结果.
我如何才能将此代码更改为我的书所希望的方式？
int main ()
{
for (int i=2; i<100; i++)
for (int j=2; j<i; j++)
{
if (i % j == 0)
break;
else if (i == j+1)
cout << i << " ";
}
return 0;
}
素数是具有两个不同除数的整数,即1和数字本身.编写,运行和测试C++程序,查找并打印小于100的所有素数.(提示:1是素数.对于每个从2到100的数字,找到Remainder = Number%n,其中n的范围是2 to sqrt(number).\如果n大于sqrt(数字),则该数字不能被n整除.为什么？如果任何剩余等于0,则该数字不是素数.)
他们究竟做了什么？我知道可能使用@(在模式匹配开始时指定一个名字),但是在〜上找不到任何东西.
我在下面的代码片段中找到了它们,取自http://www.haskell.org/haskellwiki/Prime_numbers,但是本文假设您能够熟练使用Haskell语法并且不打算解释其深奥的操作符(第一部分) '混淆是筛子宣言的开始):
primesPT () = 2 : primes'
where
primes' = sieve [3,5..] primes' 9
sieve (p:xs) ps@ ~(_:t) q
| p < q = p : sieve xs ps q
| True = sieve [x | x<-xs, rem x p /= 0] t (head t^2)
关于这里使用的语法的任何解释(或链接到一个)将不胜感激.
我是Haskell的新手.
如何生成包含下一个整数的素因子的列表列表？
现在我只知道如何生成素数:
primes = map head $ iterate (\(x:xs) -> [y | y<-xs, y `mod` x /= 0 ]) [2..]
是否有一种有效的算法来按升序排列数n的因子而不进行排序？"有效"我的意思是:
该算法通过从n的素数幂分解开始,避免了对除数的强力搜索.
算法的运行时复杂度为O(d log 2 d)或更好,其中d是n的除数.
算法的空间复杂度为O(d).
该算法避免了排序操作.也就是说,这些因素是按顺序生成的,而不是按顺序生成并随后排序.尽管使用简单的递归方法进行枚举然后排序是O(d log 2 d),但是对于排序中涉及的所有存储器访问来说,存在非常难看的成本.
一个简单的例子是n = 360 =2³×3²×5,其中d = 24个因子:{1,2,3,4,5,6,8,9,10,12,15,18,20,24, 30,36,40,45,60,72,90,120,180,360}.
一个更严重的例子是n = 278282512406132373381723386382308832000 =2⁸×3⁴×5³×7²×11²×13²×17×19×23×29×31×37×41×43×47×53×59×61×67×71×73 ×79,其中d = 318504960因子(显然这里列出太多了!).顺便提一下,这个数字具有最大数量的因子,最多可达2 ^ 128.
我可以发誓几周前我看到了这种算法的描述,带有示例代码,但现在我似乎无法在任何地方找到它.它使用了一些魔术技巧,在每个素数因子的输出列表中维护一个祖先索引列表.(更新:我使用汉明数字混淆因子生成,其运算方式类似.)
我最终在运行时使用O(d)的解决方案,具有极低的内存开销,可以就地创建O(d)输出,并且比我所知的任何其他方法都要快得多.我已经发布了这个解决方案作为答案,使用C源代码.它是另一个贡献者Will Ness在Haskell中提供的一个优化算法的优化简化版本.我选择了Will的答案作为公认的答案,因为它提供了一个非常优雅的解决方案,符合最初规定的所有要求.