标签: number-theory

获得这个的一种方法是对于自然数(1,...,n)我们将每个因子分解并查看它们是否具有任何重复的素因子,但是对于大n来说这将花费大量时间.那么有没有更好的方法来获得1,...,n的无方格数？

项目欧拉的第10个问题:

低于10的素数之和为2 + 3 + 5 + 7 = 17.

找出200万以下所有素数的总和.

我找到了这个片段:

sieve = [True] * 2000000 # Sieve is faster for 2M primes
def mark(sieve, x):
    for i in xrange(x+x, len(sieve), x):
        sieve[i] = False

for x in xrange(2, int(len(sieve) ** 0.5) + 1):
    if sieve[x]: mark(sieve, x)

print sum(i for i in xrange(2, len(sieve)) if sieve[i]) 

在这里发布 ,持续3秒.

我写了这段代码:

def isprime(n):
    for x in xrange(3, int(n**0.5)+1):
        if n % x == 0:
            return False
    return True

sum=0; …

在大多数编程竞赛中,程序的输出被认为是非常大的,通常被指示将输出除以10000007(或者在这种情况下是素数).由于在许多情况下采用素数的意义是什么我发现相同的数字是100004(即不是素数)..？

我尝试实施Lehmann测试,但它第一次没有工作.我按照每个人的描述

1. 计算r = [a ^((p -1)/ 2)] mod p
2. 如果r不是1或-1则p绝对不是素数.
3. 如果r = 1或-1,则p不是素数的可能性最多为50%.

无论我怎么做,它都无法奏效.我甚至尝试过编码

p = 7; //definitely a prime number

double e = (p - 1 )/2;

int f = (int)pow(3, e) % p;

cout << f <<endl;

f最终为6

任何帮助将不胜感激

我正在写一个遗传算法来解决Master Mind游戏.我已经对最佳方法进行了大量研究,拥有多样化的人口非常重要.我正在尝试确定如何在C++中获得非常好的随机数.我已经srand(time(NULL))在我的程序开始时设置种子然后我只是使用了rand().我想知道的是这是多么随机？它不错吗？是否还有其他更好的随机数库？

我知道数论和随机性是一个非常复杂的主题; 在编写自己的版本时,你有什么指针rand()吗？

试图在Haskell中解决项目Euler上的问题12.

通过添加自然数来生成三角数的序列.

所以第7个三角形数字是1 + 2 + 3 + 4 + 5 + 6 + 7 = 28.前十个术语是:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Run Code Online (Sandbox Code Playgroud)

让我们列出前七个三角形数字的因子:

1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28
 We can see that 28 is the first triangle number to have over five divisors.

Run Code Online (Sandbox Code Playgroud)

拥有超过500个除数的第一个三角形数的值是多少？

我的解决方案适用于少量除数(例如,给定5,它返回28),但是当输入500时,它似乎无限期地挂起.

-- Lazily generates infinite list of triangle numbers.
triangleNumbers :: [Integer]
triangleNumbers = map (\x -> sum [1..x]) [1..]

-- …

假设我有一套A={a_1, a_2, ..., a_n}.我还有一个f:AxA->R从A某个实际值中分配一对的函数.我想提取一个子集S_k的大小k 从A以使其最大程度地提高所有元素的整体成对总和S_k

是否有任何已知的算法可以在合理的时间内完成此操作？多项式/准多项式时间也许？

编辑:工作示例

假设A={a_1,a_2,a_3,a_4}with k=3和f定义为:

f(a_1,a_2)=0,f(a_1,a_3)=0,f(a_1,a_4)=0,f(a_2,a_3)=1,f(a_2,a_4)=5,f(a_3,a_4)=10.

然后,S_k={a_2,a_3,a_4}因为它最大化总和f(a_2,a_3)+f(a_2,a_4)+f(a_3,a_4).(即S_k中所有元素的成对总和)

该代码实现了一个Pollard rho()函数的示例,用于查找正整数n的因子.我已经检查了Julia"Primes"包中的一些代码,这些代码快速运行以试图加速pollard_rho()函数,但都无济于事.代码应该在大约100毫秒到30秒(Erlang,Haskell,Mercury,SWI Prolog)中执行n = 1524157897241274137,但在JuliaBox,IJulia和Julia REPL上需要大约3到4分钟.我怎样才能让它变得快速？

pollard_rho(1524157897241274137)= 1234567891

__precompile__()
module Pollard

export pollard_rho

function pollard_rho{T<:Integer}(n::T)
    f(x::T, r::T, n) = rem(((x ^ T(2)) + r), n)
    r::T = 7; x::T = 2; y::T = 11; y1::T = 11; z::T = 1
    while z == 1
        x  = f(x, r, n)
        y1 = f(y, r, n)
        y  = f(y1, r, n)
        z  = gcd(n, abs(x - y))
    end
    z >= n ? "error" : z
end

end # module

我正在尝试创建一个基本函数来测试Haskell中整数的素数.我有一些代码可以在临时意义上工作,但在我尝试将其传递给函数时会继续收到错误消息.请注意,我正在GHCi中直接编写定义,使用:{和:}.

我们的想法是创建一个N modulo {所有整数直到舍入sqrt(N)}的列表,然后测试结果列表中除初始索引之外的零.以下四个功能都有效:

rndRoot :: (Floating a, Integral c, RealFrac a) => a -> c
rndRoot = round . sqrt

oneToRndRoot :: (Floating a, Integral t, RealFrac a) => a -> [t]
oneToRndRoot x = [1..rndRoot(x)]

modulo x y
  | n < 0 = x
  | otherwise = modulo n y
  where n = x - y

mapMod x = map (modulo x)

这也有效:

mapMod 49 (oneToRndRoot 49)

然而,虽然repl接受这个定义而没有抱怨......

mapModToRndRoot x = mapMod x $ …

我想计算给定$ N $元素集的每个子集的乘积之和.例如,给定集合{1,2,3},答案是1 + 2 + 3 + 1*2 + 1*3 + 2*3 + 1*2*3.我还想给出模数$ $ M $.

我所知道的是我可以计算$(x - a_1)(x - a_2)...(x - a_n) - 1 $,但这会涉及FFT,因此可能存在一些舍入误差,但主要问题是这个想法是需要$ O(N\log ^ 2 N)$时间并且模数$ M $是有问题的.有没有更快的方法来解决这个问题？这不是我的功课,我从老师那里得到了这个任务来练习编程比赛,但我真的遇到了这个问题.

约束:

$ a_i\le 10 ^ 9 $

$ N\le 10 ^ 6 $

$ M\le 10 ^ 9 $