标签: primes

你能否建议一种在实践中可用的快速,确定性的方法,用于测试大数是否为素数？

另外,我想知道如何正确使用非确定性素性测试.例如,如果我使用这样的方法,如果输出为"no",我可以确定数字不是素数,但是当输出"可能"时,另一种情况呢？在这种情况下,我是否必须手动测试素数？

提前致谢.

我正在为Diffie-Hellman类型密钥生成2048位安全素数,p使得p和(p-1)/ 2都是素数.

我可以在p和(p-1)/ 2上使用几次Rabin-Miller迭代,并且仍然对加密密钥有信心吗？在我做过的研究中,我已经听到了1024位普通素数的6到64次迭代的所有内容,所以我在这一点上有点困惑.一旦确定,如果您正在生成一个安全的素数而不是普通素数,那么数字是否会改变？

计算时间非常宝贵,所以这是一个实际的问题 - 我基本上想知道如何找到尽可能少的测试数量,同时保持非常有保障的安全性.

我一直在测试竞争性编程的水域,我已经看过很多次提到的这个陈述:

打印结果模10 ⁹ + 7

现在我可以弄清楚这是一种在处理非常大的数字时防止数字溢出的方法.但它是如何以及为什么有效？如果有人能解释这背后的数学推理,我将不胜感激.

我正在尝试通过Project Euler工作,我在问题03上遇到障碍.我有一个适用于较小数字的算法,但问题3使用非常非常大的数字.

问题03: 13195的主要因素是5,7,13和29. 600851475143中最大的素数因子是什么？

这是我在C#中的解决方案,它一直在运行,我认为接近一个小时.我不是在寻找答案,因为我确实想自己解决这个问题.主要是寻求一些帮助.

    static void Main(string[] args) {
        const long n = 600851475143;
        //const long n = 13195;
        long count, half, largestPrime = 0;
        bool IsAPrime;

        half = n / 2;

        for (long i = half; i > 1 && largestPrime == 0; i--) {
             if (n % i == 0) { // these are factors of n
                count = 1;
                IsAPrime = true;
                while (++count < i && IsAPrime) {
                    if (i % count == 0) …

我们在工作中有点乐趣.这一切都始于其中一个设置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个素数上限的好方法.)

从这篇文章来看,

/^1?$|^(11+?)\1+$/ 检查一个数字(它在一元中的值)是否为素数.

使用它,perl -l -e '(1 x $_) !~ /^1?$|^(11+?)\1+$/ && print while ++$_;'返回素数列表.

我没有足够的Perl经验,但据我所知,正则表达式对于非素数的数字都是正确的.因此,如果我们使用此表达式打印所有不产生true的数字,我们会有一个素数列表.这就是perl查询尝试做的事情.

关于正则表达式部分,

^1?$部分用于计算1 不是素数

^(11+?)\1+$ 用于匹配从4开始的非素数.

我不明白的是为什么?正则表达式需要.据我说,/^1$|^(11+)\1+$/应该很好,实际上

perl -l -e '(1 x $_) !~ /^1$|^(11+)\1+$/ && print while ++$_;' 给了我相同的素数集.

我对正则表达式的理解有什么缺陷吗？为什么?需要？

是不是?应该匹配前面的表达式的零或一次出现？

我用Java编写了一个计算2的幂的程序,但它看起来非常低效.对于较小的功率(比如2 ^ 4000),它可以在不到一秒的时间内完成.但是,我正在考虑计算2 ^ 43112609,这比最大的已知素数大一个.超过1200万个数字,运行需要很长时间.到目前为止,这是我的代码:

import java.io.*;

public class Power
{
 private static byte x = 2;
 private static int y = 43112609;
 private static byte[] a = {x};
 private static byte[] b = {1};
 private static byte[] product;
 private static int size = 2;
 private static int prev = 1;
 private static int count = 0;
 private static int delay = 0;
 public static void main(String[] args) throws IOException
 {
  File f = new File("number.txt");
  FileOutputStream output = new …

可能的重复:
第n个丑陋的数字
找到表达式的第K个最小数(2 ^ x)*(3 ^ y)*(5 ^ z)

我想知道如何以快速和优雅的方式解决这个问题:

我们定义"丑陋"的每个数字n可以用以下形式写出:2 ^ x*3 ^ y*5 ^ z ;,其中x,y和z是自然数.找到第1500个丑陋的数字.

例如,第一个"丑陋"的数字是:

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...

我试图用暴力解决这个问题,这样:

import itertools as it

def is_ugly(n):
    '''Return `True` if *n* is an ugly number.'''

    if n == 1:
        return True
    while not n % 2:
        n //= 2
    while not n % 3:
        n //= 3
    while not n % 5:
        n //= 5
    return n …

我注意到F#和C#中看似相同的代码不会执行相同的操作.F#的数量级更慢.作为一个例子,我提供的代码生成素数/给出F#和C#中的第n个素数.我的F#代码是:

let rec isprime x =
primes
|> Seq.takeWhile (fun i -> i*i <= x)
|> Seq.forall (fun i -> x%i <> 0)

and primes = 
    seq {
        yield 2
        yield! (Seq.unfold (fun i -> Some(i, i+2)) 3)
                |> Seq.filter isprime
    }


let n = 1000
let start = System.DateTime.Now
printfn "%d" (primes |> Seq.nth n)
let duration = System.DateTime.Now - start
printfn "Elapsed Time: "
System.Console.WriteLine duration

而C#看起来像这样:

class Program
{
    static bool isprime(int n)
    {
        foreach (int p …