标签: number-theory

我正在解决Haskell中的一些经典问题以开发我的功能技能,我在实现这个"Programming Praxis"网站上建议的优化时遇到了问题:

我有三个解决这个问题的方法,第三个解决方案与第二个解决方案相比太慢.有人可以对我的代码提出一些改进吗？

我的实现是:

-- primeira implementação
primes n
    | n < 2 = []
    | n == 2 = [2]
    | n `mod` 2 == 0 = primes'
    | otherwise = if (find (\x -> n `mod` x == 0) primes') == Nothing then
                      n:primes'
                  else
                      primes'
    where primes' = primes (n - 1)

-- segunda implementação
primes' :: Integer -> [Integer]
primes' n = sieve $ 2 : [3,5..n]
    where sieve :: [Integer] -> [Integer]
          sieve …

你会如何生成一个非常大的随机数？我正在思考2 ^ 10 ^ 9(十亿位)的顺序.任何编程语言 - 我认为该解决方案将转换为其他语言.

我想在[1,N]上统一分布.

我最初的想法:

- 你可以随机生成每个数字并连接.问题:即使非常好的伪随机生成器也可能开发出数百万位数的模式,对吗？

• 您可以通过将随机数提高到随机指数来帮助创建大的随机数.问题:你必须使数学工作,以便得到的数字仍然是随机的,你应该能够在合理的时间内(比如一小时)计算它.

• 如果它有帮助,你可以尝试在可能更小的范围(例如使用实数)和变换上生成可能不均匀的分布.问题:这可能同样困难.

有任何想法吗？

问题:http://www.spoj.com/problems/DIVREL

问题是,我们只需要从给定的一组元素中找到不是倍数(可以被b形式整除)的元素的最大数量.如果我们只是从一个元素到它的多个边缘并构造一个图形,那么它将是一个DAG.

现在问题只是改变为找到包含所有顶点的链的最小数量,这些顶点使用Dilworth定理等于antichain基数,因为它是一个部分有序的集合.

使用二分匹配可以找到最小链(如何:它是最小路径覆盖)但现在我无法找到自身的反链元素？

作为一个业余爱好项目,我正在努力寻找真正庞大的素数.对此的素性测试包含模幂运算,即a ^ modn.让我们称之为modpow操作,以使解释变得简单.我想加快这个特定的计算.

目前我正在使用GMP的mpz_pown函数,但是,它有点慢.我认为它太慢的原因是因为对GMP的modpow的函数调用比对相同大数字的PFGW软件的完整素性测试要慢.(所以要清楚,这只是GMP的modpow部分,而不是我正在比较的整个自定义素性测试程序).PFGW被认为是其领域中最快的,对于我的用例,它使用了Brillhart-Lehmer-Selfridge素性测试 - 它也使用了modpow程序 - 所以不是因为数学上的聪明,PFGW在这方面更快(请纠正我,如果我错了.)看起来GMP的瓶颈是modpow操作.数字的示例运行时间略超过20,000个数字:GMP的modpow操作大约需要45秒,而PFGW在9秒内完成整个素数测试(包括一个modpow).对于更大的数字,差异变得更加令人印象深刻.GMP使用FFT乘法和蒙哥马利减少进行此测试比较,请参阅下面这篇文章的评论.

我做了一些研究.到目前为止,我理解modpow算法通过平方,整数乘法和模数减少使用取幂 - 这些对我来说都非常熟悉.几种辅助方法可以改善整数乘法的运行时间:

• 蒙哥马利乘法
• FFT乘法

为了通过平方部分来改善取幂的运行时间,可以使用有符号的数字表示来减少乘法的数量(即,比特表示为0,1或-1,并且比特串以这样的方式表示,使得它包含的零比原始的base-2表示更多 - 这通过平方减少了求幂的运行时间.

为了优化操作的模数部分,我知道这些方法:

• 蒙哥马利减少

所以这是150,000美元的问题:有一个软件库可以在给定非常大的基数,指数和模数的情况下有效地进行modpow操作吗？(我的目标是数百万的数字).如果您想建议一个选项,请尝试解释算法的内部工作原理,包括基数,模数和指数的数百万位数,因为有些库根据位数使用不同的算法.基本上我正在寻找一个支持上述技术的库(或者可能更聪明的技术),并且它在运行算法时应该运行良好(至少比GMP好).到目前为止,我已经搜索,发现并尝试了GMP和PFGW,但没有发现这些令人满意(PFGW很快,但我只对modpow操作感兴趣并且没有直接的编程接口).我希望可能是该领域的专家可以建议具有这些功能的库,因为似乎很少有能够处理这些要求的库.

编辑:使问题更简洁,因为它标记得太宽泛.

给定数字X,计算该数字的素因子乘积的最有效方法是什么？有没有办法在没有实际分解的情况下做到这一点？注意 - 需要素数因子的乘积(全部是功率统一).

编写一个带整数的程序,并打印出所有方法来乘以等于原始数字的较小整数,而不重复多组因子.换句话说,如果您的输出包含4*3,则不应再次打印3*4,因为这将是重复集.请注意,这不是仅要求素数分解.此外,您可以假设输入整数的大小合理; 正确性比效率更重要.PrintFactors(12)12*1 6*2 4*3 3*2*2

public void printFactors(int number) {
    printFactors("", number, number);
}

public void printFactors(String expression, int dividend, int previous) {
    if(expression == "")
        System.out.println(previous + " * 1");

    for (int factor = dividend - 1; factor >= 2; --factor) {
        if (dividend % factor == 0 && factor <= previous) {
            int next = dividend / factor;
            if (next <= factor)
                if (next <= previous)
                    System.out.println(expression + factor + " * " + next);

            printFactors(expression + factor …

我在C#中编写了一个程序,以便在一定范围内找到完美的数字,作为编程挑战的一部分.但是,我意识到计算10000以上的完美数字时速度非常慢.有没有找到完美数字的优化方法？我的代码如下:

using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleTest
{
 class Program
 {
  public static List<int> FindDivisors(int inputNo)
  {
   List<int> Divisors = new List<int>();
   for (int i = 1; i<inputNo; i++)
   {
    if (inputNo%i==0)
     Divisors.Add(i);
   }
   return Divisors;
  }

  public static void Main(string[] args)
  { 
   const int limit = 100000;

   List<int> PerfectNumbers = new List<int>();
   List<int> Divisors=new List<int>();
   for (int i=1; i<limit; i++)
   {
    Divisors = FindDivisors(i);
    if (i==Divisors.Sum())
     PerfectNumbers.Add(i);
   }

   Console.Write("Output =");

   for (int i=0; i<PerfectNumbers.Count; i++)
   {
    Console.Write(" …

我是 C++ 的绝对初学者。字面上地。刚刚过去一周了。今天我正在编写一个程序来测试需要多少次迭代才能使某个数字成为回文。这是代码：

#include <iostream>
#include <string>
#include <algorithm>

/*  This program calculates the steps needed
    to make a certain number palindromic.
    It is designed to output the values for
    numbers 1 to 1000
*/
using namespace std;

class number
{
public:
    string value;
    void reverse();
};

void number::reverse()
{
    std::reverse(value.begin(),value.end());
}

void palindrome(number num)
{
    string n=num.value;
    number reversenum, numsum, numsumreverse;
    reversenum=num;
    reversenum.reverse();
    numsum.value=num.value;
    numsumreverse.value=numsum.value;
    numsumreverse.reverse();
    int i=0;
    while (numsum.value.compare(numsumreverse.value) !=0)
    {
        reversenum=num;
        reversenum.reverse();
        numsum.value=to_string(stoll(num.value,0,10)+stoll(reversenum.value,0,10));
        numsumreverse.value=numsum.value;
        numsumreverse.reverse();
        num.value=numsum.value;
        i++; …

问题来了——我得到了一个质数 P 和一个数 K。我需要计算 P ^ P ^ P ... k 次模到 m。

这里P是素数。

(P ^ (P ^ (P ^ P .... k times))) % m

几个例子

对于 P = 2, K = 3, m = 3

2 ^ 2 ^ 2 % 3 = 1

对于 P = 5，K = 3，m = 3

5 ^ 5 ^ 5 % 3 = 2

我可以使用蛮力，但问题是数字会变得非常大。

这是限制条件

2 <= p < 10 ^ 8
1 <= k < 10 ^ 8 
1 …

给定一个正整数 n，找到最大整数 a，使得 a*a 整除 n。

如果你知道 n 的因式分解，那就相当简单了。问题是，它是否可以比使用最知名的方法对 n 进行因式分解更快地完成？有没有多项式算法？（位长为 n 的多项式）

例如，使用 Pollard 的 rho 分解算法，它将在 O(n^(1/4)) 中运行，但我正在寻找更好的算法。