标签: primes

昨天我在一些业余时间开始看F#.我想我会从打印出所有素数达到100的标准问题开始.继续我想出的......

#light
open System

let mutable divisable = false
let mutable j = 2

for i = 2 to 100 do
    j <- 2
    while j < i do
        if i % j = 0 then divisable <- true
        j <- j + 1

    if divisable = false then Console.WriteLine(i)
    divisable <- false

问题是我觉得我已经从C/C#的角度来看待这个并没有接受真正的功能语言方面.

我想知道其他人能想出什么 - 以及是否有人有任何提示/指针/建议.我感觉很好F#内容目前在网上很难获得,而我所触及的最后一种功能语言是约5年前大学时的HOPE.

我是C#的初学者,我正在尝试编写一个应用程序来获取用户输入的两个数字之间的素数.问题是:在大数(有效数字在1到1000000000范围内)时,获取素数需要很长时间,并且根据我正在解决的问题,整个操作必须在很短的时间间隔内进行.这是问题链接以获得更多解释: SPOJ-Prime

这是我的代码中负责获取素数的部分:

  public void GetPrime()
    {            
        int L1 = int.Parse(Limits[0]);
        int L2 = int.Parse(Limits[1]);

        if (L1 == 1)
        {
            L1++;
        }

        for (int i = L1; i <= L2; i++)
        {
            for (int k = L1; k <= L2; k++)
            {
                if (i == k)
                {
                    continue;
                }
                else if (i % k == 0)
                {
                    flag = false;
                    break;
                }
                else
                {
                    flag = true;
                }
            }

            if (flag)
            {
                Console.WriteLine(i);
            }
        }
    }

有没有更快的算法？提前致谢.

好吧,我对RSA数学运算的理解可能不会那么深,所以如果这是愚蠢的话,请随意拍我的头:

要生成私钥,我们需要两个随机的大素数.没有算法可以精确有效地做到这一点,但是有些算法可以生成大数字,这些数字具有99.99999 ...(数十亿9s)... 999%的概率.

我的问题是:如果通过一个惊人的运气,当你生成你的密钥时,素数生成算法产生了一个非素数会发生什么？这对于使用这个不幸的密钥的软件有何影响？

编辑:我知道其他因素更可能是这个问题的不良结果来源; 这只是纯粹的书呆子数学好奇心.

在J.Brian Conrey在图6中的论文"The Riemann Hypothesis"中,有一个素数定理中误差项的傅立叶变换图.请参见下图中左侧的图:

在由Chris King撰写的名为Primes out of Thin Air的博客文章中,有一个Matlab程序可以绘制频谱图.请参阅帖子开头右侧的情节.可以翻译成Mathematica:

数学:

 scale = 10^6;
 start = 1;
 fin = 50;
 its = 490;
 xres = 600;
 y = N[Accumulate[Table[MangoldtLambda[i], {i, 1, scale}]], 10];
 x = scale;
 a = 1;
 myspan = 800;
 xres = 4000;
 xx = N[Range[a, myspan, (myspan - a)/(xres - 1)]];
 stpval = 10^4;
 F = Range[1, xres]*0;

For[t = 1, t <= xres, t++,
 For[yy=0, yy<=Log[x], yy+=1/stpval,
 F[[t]] =
 F[[t]] +
 Sin[t*myspan/xres*yy]*(y[[Floor[Exp[yy]]]] …

任何人都可以帮我解决布伦特的循环检测算法.我不明白为什么"寻找比λ和μ都大的两个2 ^ i的最小功率"？2的权力如何在循环的检测中发挥作用.它是否与Floyd的循环检测算法有某种关系？我无法从基础知识中获得它.请帮忙 !

我已经阅读了过去几个小时的哈希码函数,并且在自定义哈希码实现中使用素数作为乘数已经积累了一些问题.如果我能对以下问题有所了解,我将不胜感激:

• 在对@ mattb的答案的评论中,@ hstoerr主张使用更大的素数(例如524287)而不是公共素数31.我的问题是,给定一对或元素的哈希码函数的以下实现:

  @Override
  public int hashCode() {
      final int prime = 31;
      int hash1 = (pg1 == null) ? 0 : pg1.hashCode();
      int hash2 = (pg2 == null) ? 0 : pg2.hashCode();
      return prime * (hash1 ^ hash2);
  }
  

  Run Code Online (Sandbox Code Playgroud)

这不会导致返回的溢出,int如果prime是大数？

• 假设溢出是没有问题的(JVM做一个自动施法)是它更好地做一个位位移,而不是一个演员？

• 我认为哈希码函数的性能根据哈希码的复杂性而有很大差异.主乘数的大小是否不影响性能？

• 在自定义哈希码函数中使用多个素数而不是单个乘法器更好/更智能/更快？如果没有,还有其他一些优势吗？请参阅@ jinguy对相关问题的回答中的示例:

  public int hashCode() {
      return a * 13 + b.hashCode() * 23 + (c? 31: 7);
  }
  

  Run Code Online (Sandbox Code Playgroud)

其中a是一个int,b是一个 …

这是功能:

var isPrime = function(x) {
    return (!(/^,?$|^(,,+?)\1+$/.test(Array(++x))));
};

它适用于小数字,但是当数字很大时,会抛出一个异常,表示数组长度无效.我无法理解这里发生了什么.RegEx测试的作用是什么？为什么这段代码有效？

我认为F#意味着比C#更快,我做了一个可能不好的基准测试工具,C#得到16239ms,而F#做得更差,为49583ms.有人可以解释为什么会这样吗？我正在考虑离开F#并回到C#.是否可以通过更快的代码在F#中获得相同的结果？

这是我使用的代码,我尽可能地使它成为平等.

F#(49583ms)

open System
open System.Diagnostics

let stopwatch = new Stopwatch()
stopwatch.Start()

let mutable isPrime = true

for i in 2 .. 100000 do
    for j in 2 .. i do
        if i <> j && i % j = 0 then
            isPrime <- false
    if isPrime then
        printfn "%i" i
    isPrime <- true

stopwatch.Stop()
printfn "Elapsed time: %ims" stopwatch.ElapsedMilliseconds

Console.ReadKey() |> ignore

C#(16239ms)

using System;
using System.Diagnostics;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        { …

我正在玩并尝试编写RSA的实现.问题在于我不得不生成生成密钥对所涉及的大量素数.有人能指出我快速生成巨大的素数/可能的素数吗？

我是编程世界的新手.我只是在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