为什么这段代码会返回一个数字因子的总和？
在几个Project Euler问题中,您被要求计算因子的总和作为问题的一部分.在那里的一个论坛上,有人发布了以下Java代码作为查找总和的最佳方式,因为你实际上不需要找到个别因素,只需要找到主要因素(你不需要知道Java,你可以跳到下面的摘要):
public int sumOfDivisors(int n)
{
int prod=1;
for(int k=2;k*k<=n;k++){
int p=1;
while(n%k==0){
p=p*k+1;
n/=k;
}
prod*=p;
}
if(n>1)
prod*=1+n;
return prod;
}
现在,我已经尝试了很多次,我发现它有效.问题是,为什么？
说你因素100: 1,2,4,5,10,20,25,50,100.总和是217.主要因素分解是2*2*5*5.这个功能给你[5*(5+1)+1]*[2*(2+1)+1] = [25+5+1]*[4+2+1] = 217
保理8:1,2,4,8.总和是15.主要因素分解是2*2*2.这个功能给你[2*(2*(2+1)+1)+1]=15
该算法归结为(Fi用于表示因子F或F sub i的第i个索引):
return product(sum(Fi^k, k from 0 to Ni), i from 1 to m)
其中m,唯一素因子Ni的数量是每个唯一因子在素数因子分解中出现的次数.
为什么这个公式等于因子的总和？我的猜测是,它等于通过分配属性的每个独特的素因子组合(即每个独特因子)的总和,但我不知道如何.
在开始之前,让我说:这不是功课,只是简单,陈旧,有趣.
现在,我试图想出一个能够回答这个问题的算法1/x + 1/y = 1/n!.
正如您在上面的链接中所看到的,作者只询问提示而不是实际答案,所以我会请求同样的.
我将表达式简化为(x - n!)(y - n!)=(n!)^ 2,如其中一个答案所示,到那时我理解了(x,y)对的组合数与n!^ 2的除数数相同(如果我错了,请纠正我).
所以,正如接受的答案所暗示的那样,我试图得到每个素数组成N!^ 2的所有因子的乘法.
我在C中使用试验分区得出了一些代码来分解N!^ 2和Eratosthenes的Sieve以获得所有素数达到sqrt(N!^ 2).
现在的问题是内存,我试过N = 15而我的Mac(四核6GB内存)几乎死在我身上.问题是记忆力.所以我添加了一些printf并尝试使用N = 11:
Sieve of Eratosthenes took 13339.910000 ms and used 152 mb of memory
n= 11; n!^2 = 1593350922240000; d = 6885
[2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,5,5,5,5,7,7,11,11]
该列表是N!^ 2的所有主要因素(当然除了1和N!^ 2).
我想要一些关于如何最小化内存消耗和可能的优化的提示.
代码吼叫,这只是一个快速实验,所以我确信它可以优化.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <strings.h>
#include <sys/time.h>
#include <assert.h>
//Linked List
struct node {
struct …我马上给出一个例子,现在假设我有3个数组a,b,c等
a = c(3,5)
b = c(6,1,8,7)
c = c(4,2,9)
我必须能够在它们之间提取连续的三元组,例如,
c(1,2,3),c(4,5,6)
但这仅仅是一个例子,我将拥有一个甚至超过10个数组的更大的数据集,因此必须能够找到连续的十个长度系列.
因此,任何人都可以提供算法,通常在'n'数组中找到连续的长度'n'系列.
我实际上在R中做这个东西,所以如果你用R代码你的代码它更可取.但是来自任何语言的算法都非常受欢迎.
这是问题(四个总和的总和)指出:
输入在每一行中包含一个整数N(N <= 10000000).这是您必须表示的四个素数的总和
样本输入:
24
36
46样本输出:
3 11 3 7
3 7 13 13
11 11 17 7
乍一看,我想到了这个想法
但我觉得这种算法的复杂性非常糟糕.这个问题看起来也像Goldbach's_conjecture .我怎么解决这个问题？
你会如何生成一个非常大的随机数？我正在思考2 ^ 10 ^ 9(十亿位)的顺序.任何编程语言 - 我认为该解决方案将转换为其他语言.
我想在[1,N]上统一分布.
我最初的想法:
- 你可以随机生成每个数字并连接.问题:即使非常好的伪随机生成器也可能开发出数百万位数的模式,对吗？
您可以通过将随机数提高到随机指数来帮助创建大的随机数.问题:你必须使数学工作,以便得到的数字仍然是随机的,你应该能够在合理的时间内(比如一小时)计算它.
如果它有帮助,你可以尝试在可能更小的范围(例如使用实数)和变换上生成可能不均匀的分布.问题:这可能同样困难.
有任何想法吗？
所以我正在尝试做一些数论工作,我正在使用Mathematica,但认为Haskell更适合处理无限列表(因为AFAIK Mathematica没有懒惰的评估).我想要做的是让Haskell在无限懒惰列表中存储1/x的所有数字.到目前为止,我的搜索还没有找到一种方法将比率分成数字,返回数字列表而不是实际的浮点数.
所述循环迭代领导算法是用于通过移动所有偶数项的前部和所有奇数项至背面,同时保持它们的相对次序混洗的阵列的算法.例如,给定此输入:
a 1 b 2 c 3 d 4 e 5
输出将是
a b c d e 1 2 3 4 5
该算法在O(n)时间内运行,仅使用O(1)空间.
该算法的一个不寻常的细节是它通过将阵列分成大小为3k + 1的块来工作.显然这对于算法正常工作至关重要,但我不知道为什么会这样.
为什么算法中需要选择3 k + 1？
谢谢!
我有三个N位号,A,B,和C.我不能轻易计算,(A + B) % C但我可以轻松计算A % C和B % C.如果模运算是无符号的,并且我提前知道A + B没有包围N位,那么我可以改为计算((A % C) + (B % C)) % C.但是,是否可以对模数操作签名或添加A并B可能导致环绕的情况执行任何操作.
看起来可能存在一些混淆,为什么((A % C) + (B % C)) % C不能依赖它始终工作.这是一个未签名的示例:
unsigned A = 0x1U;
unsigned B = 0xFFFFFFFFU;
unsigned C = 0x3U;
((A % C) + (B % C)) % C == 0x1U but (A + …注意:2015年6月17日更新.当然这是可能的.请参阅以下解决方案.
即使有人复制并粘贴此代码,您仍然需要进行大量清理工作.另请注意,从Re(s)= 0到Re(s)= 1 :),关键条带内部会出现问题.但这是一个好的开始.
import java.util.Scanner;
public class NewTest{
public static void main(String[] args) {
RiemannZetaMain func = new RiemannZetaMain();
double s = 0;
double start, stop, totalTime;
Scanner scan = new Scanner(System.in);
System.out.print("Enter the value of s inside the Riemann Zeta Function: ");
try {
s = scan.nextDouble();
}
catch (Exception e) {
System.out.println("You must enter a positive integer greater than 1.");
}
start = System.currentTimeMillis();
if (s <= 0)
System.out.println("Value for the Zeta Function = " + …从数学原理:
数字N可表示为2个平方的总和,当且仅当在N的素数因子分解中,形式的每个素数都
(4k+3)出现偶数次!
我所做的是预先计算所有4k+3数字并通过连续分割检查它的频率.
该程序是根据约束编写的:
1 < T <100
0 < N < 10 ^ 12
import java.util.Scanner;
public class TwoSquaresOrNot {
static int max = 250000;
static long[] nums = new long[max];
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int i = 0; i < max; ++i)
nums[i] = 4 * i + 3;
while (T-- > 0) {
long n = sc.nextLong();
System.out.println((canWrite(n) ? "Yes" : …