标签: prime-factoring

在开始之前,让我说:这不是功课,只是简单,陈旧,有趣.

现在,我试图想出一个能够回答这个问题的算法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 …

我正在用C编写一个代码,它返回一个正整数可以表示为两个正整数的完美平方和的次数.

R(n) is the number of couples (x,y) such that x² + y² = n where x, y, n are all 
non negative integers.

为了计算R(n),我需要首先找到n的素因子分解.

问题是我已经尝试了许多我可以在C上使用的素数因子分解算法,但是我需要尽可能快地使用我的代码,所以如果有人能给我他/她认为的那样我会很感激最快的算法来计算大数的素数因子化 2147483742.

我正在尝试自学clojure,我正在使用Prime Factor Kata和TDD的原则来实现这一目标.

通过一系列像这样的Midje测试:

(fact (primefactors 1) => (list))

(fact (primefactors 2) => (list 2))

(fact (primefactors 3) => (list 3))

(fact (primefactors 4) => (list 2 2))

我能够创建以下功能:

(defn primefactors 
    ([n] (primefactors n 2))
    ([n candidate] 
        (cond (<= n 1) (list)
              (= 0 (rem n candidate)) (conj (primefactors (/ n candidate)) candidate)
              :else (primefactors n (inc candidate))
        )
    )
)

这很有效,直到我抛出以下边缘案例测试:

(fact (primefactors 1000001) => (list 101 9901))

我最终得到了堆栈溢出错误.我知道我需要将其转换为适当的重复循环,但我看到的所有示例似乎都过于简单,仅指向计数器或数值变量作为焦点.如何进行递归？

谢谢!

我需要编写一个程序来输入一个数字并以下面的形式输出它的阶乘:

4!=(2 ^ 3)*(3 ^ 1)

5!=(2 ^ 3)(3 ^ 1)(5 ^ 1)

问题是我仍然无法弄清楚如何得到这个结果.显然,括号中的每个第一个数字都是上升的素数,直到实际的阶乘.括号中的第二个数字是该数字在阶乘中出现的次数.

我无法弄清楚的是例如5!=(2 ^ 3)(3 ^ 1)(5 ^ 1),2如何仅出现3次,3次仅1次,5次仅120次( 5!= 120).

我现在已经解决了这个问题,感谢有帮助的人评论但我现在无法弄清楚我怎么能得到一个数字并以这种格式得到阶乘而不实际计算阶乘.

我在我找到的网站上做了这个问题(项目Euler),并且有一个问题涉及找到一个数字的最大素数因子.我的解决方案失败了很多,所以我想知道如何简化这段代码？

""" Find the largest prime of a number """


def get_factors(number):
    factors = []
    for integer in range(1, number + 1):
        if number%integer == 0:
            factors.append(integer)
    return factors

def test_prime(number):
    prime = True
    for i in range(1, number + 1):
        if i!=1 and i!=2 and i!=number:
            if number%i == 0:
                prime = False
    return prime

def test_for_primes(lst):
    primes = []
    for i in lst:
        if test_prime(i):
            primes.append(i)
    return primes


################################################### program starts here
def find_largest_prime_factor(i):
    factors = get_factors(i)
    prime_factors …

我一直在python中编写一个简单的程序,使用Gödel的编码将字符串编码为数字.这是一个快速概述:你取字符串的第一个字母,找到它在字母表中的位置(a - > 1,b - > 2,...,z - > 26)并将第一个素数(2)提高到这种力量.你取字符串中的第二个字母和第二个素数(3),依此类推.这是代码:

import string, math
alphabet = list(string.ascii_lowercase)

def primes(n):
    "Returns a list of primes up to n."

    primes = [2, 3]
    i = 5
    while i < n:
        l = math.ceil(math.sqrt(i))
        k = math.ceil(math.sqrt(i+2))
        for p in primes[:l]:
            if i % p == 0:
                break
        else:
            primes.append(i)
        for p in primes[:k]:
            if (i+2) % p == 0:
                break
        else:
            primes.append(i+2)
        i += 6
    return primes

def Encode(string):
    "Encodes a …

我目前正在尝试将Java 8的Stream API合并到我的日常Java工具箱中.我正在尝试使用Streams来查找正整数的素因子,然后将每个因子存储在数组(或ArrayList)中,并将它们的多重性存储在并行数组中.或者,我正在尝试创建一个说... FactorWithMultiplicity对象的流,或者甚至Map用因子作为键,多重性作为值.如果因子按升序排序,如果它甚至可以处理非常大的数字(例如,我敢说,那么Long.MAX_VALUE)会很好.

目前,我的代码看起来像这样,但是,由于我是Streams的初学者,我确信有更快或更适合的方式来完成此任务.请使用Streams创建您的解决方案,但如果您知道某些非Stream解决方案更快,请随时向我指出该代码.

int num = getPositiveInt();
ArrayList<Integer> factors = new ArrayList<>();
ArrayList<Integer> multiplicities = new ArrayList<>();
boolean isPrime = IntStream.rangeClosed(2, num / 2)
    .reduce(num, (int temp, int factor) -> {
        int count = 0;
        while (temp % factor == 0) {
            temp /= factor;
            count++;
        }
        if (count > 0) {
            factors.add(factor);
            multiplicities.add(count);
        }
        return temp;
    }) > 1;

以下代码段计算给定数字的素数因子:

public static LinkedList<Long> getPrimeFactors(Long number) {
    LinkedList<Long> primeFactors = new LinkedList<Long>();

    for (Long factor = Long.valueOf(2); factor <= number / factor; factor++) {
        if (number % factor == 0) {
            primeFactors.add(factor);
            while (number % factor == 0) {                  
                number /= factor;
            }
        }           
    }

    if (number > 1) {
        primeFactors.add(number);
    }

    return primeFactors;
}

计算9223372036854775783的素数因子需要140937ms(这是最后的素数小于Long.MAX_VALUE).有没有办法通过并发实现这种分解,即使用ExecutorService？

编辑:

public static void getPrimeFactors(Long number) {
    LinkedList<Long> primeFactors = new LinkedList<Long>();

    if (number % 2 == 0) {
        primeFactors.add(2L); …

我正在尝试测试以下因子分解函数,但它正在为大量素数爆发:

(defn divides? [N n]
  (zero? (mod N n)))

(defn f-reduce [n f & {:keys [expt] :or {expt 0}}]
  (if (divides? n f) (f-reduce (/ n f) f :expt (inc expt))
                     (if (zero? expt) [n []] [n [f expt]])))

(defn _factors [n f known-fs]
  (let [[m fs] (f-reduce n f)]
    (if (> f (Math/sqrt m))
      (cond (and (empty? fs) (= m 1)) known-fs
            (empty? fs)               (concat known-fs [m 1])
            (= m 1)                   (concat known-fs [f (last fs)])
            true                      (concat known-fs …

我正在尝试在Haskell中实现Pollard Rho分解方法.这是我来的

func :: Int -> Int -> Int
func x n = mod ( x * x - 1) n

pollardStep :: Int -> Int -> Int -> Int -> Int -> Int
pollardStep i k n x y
      | d /= 1 && d /= n = d
      | i == k = pollardStep (i+1) (2*k) n x1 x1
      | otherwise = pollardStep (i+1) k n x1 y
      where d = gcd n $ abs $ …