标签: prime-factoring

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

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); …

#include <iostream>
using namespace std;

void whosprime(long long x)
{
    bool imPrime = true;

    for(int i = 1; i <= x; i++)
    {
        for(int z = 2; z <= x; z++)
        {
            if((i != z) && (i%z == 0))
            {
                imPrime = false;
                break;
            }
        }

        if(imPrime && x%i == 0)
            cout << i << endl;

        imPrime = true;
    }    
}

int main()
{
    long long r = 600851475143LL;
    whosprime(r);  
}

我试图 在项目Euler上找到问题3指定的数字600851475143的素因子(它要求最高的素因子,但我想找到所有这些因素).但是,当我尝试运行此程序时,我没有得到任何结果.这与我的程序花费多长时间,甚至数字本身有什么关系？

另外,有哪些更有效的方法可以解决这个问题,你有什么建议可以解决这些更优雅的解决方案,因为我正在解决这个问题吗？

一如既往,谢谢!

可能重复:
一个数字,因为它是素数部分

我有我的这个家庭作业,很难得,我必须得到给定数字的所有不同的主要分区.例如,数字7有五个不同的主要分区(或者表示它具有的2个主要分区的五种不同方式):

• 5 + 2
• 2 + 5
• 3 + 2 + 2
• 2 + 3 + 2
• 2 + 2 + 3

正如您所看到的,数字本身被排除在它是素数的情况下.我不必打印所有不同的分区,只打印它们的数量.

所以我有点迷失了.我完全无法生成任何代码,但我认为我应该从动态编程视图中解决这个问题.我只想要一些提示.有没有人有想法？提前致谢.

最高输入数为100.此外,程序的运行时间不能超过1秒,内存限制为128 MB.

为什么打印的负数为-147982099而不是8462696833 = 600851475143/71

import Data.List

smallFactor n = case (elemIndex 0 (map (mod n) [2..])) of
                    Just x -> x + 2

main = print( quot n (smallFactor n) )
    where n = 600851475143

完整输出:

$ ghc --make p3; ./p3
[1 of 1] Compiling Main             ( p3.hs, p3.o )
Linking p3 ...
-147982099

我一直在研究一个小问题,我需要将18位数字计算到它们各自的素数分解中.考虑到它确实有效,所有的东西都会编译并运行得很好,但我希望减少素数分解的运行时间.我已经实现了递归和线程,但我想我可能需要一些帮助来理解大数计算的可能算法.

每次我在预制的4个数字上运行时,大约需要10秒钟.如果有任何想法,我想减少到0.06秒.

我注意到了一些像Eratosthenes筛选的算法,并在计算之前生成了所有素数的列表.我只是想知道是否有人可以详细说明.例如,我在理解如何将Eratosthenes的Sieve实现到我的程序中或者它是否是一个好主意时遇到了问题.关于如何更好地接近这一点的任何和所有指针都会非常有用!

这是我的代码:

#include <iostream>
#include <thread>
#include <vector>
#include <chrono>

using namespace std;
using namespace std::chrono;

vector<thread> threads;
vector<long long> inputVector;
bool developer = false; 
vector<unsigned long long> factor_base;
vector<long long> primeVector;

class PrimeNumber
{
    long long initValue;        // the number being prime factored
    vector<long long> factors;  // all of the factor values
public:
    void setInitValue(long long n)
    {
        initValue = n;
    }
    void addToVector(long long m)
    {
        factors.push_back(m);
    }
    void setVector(vector<long long> m) …

我正在尝试在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 $ …

isqrt :: Integer -> Integer
isqrt = floor . sqrt . fromIntegral

primes :: [Integer]
primes = sieve [2..] where
 sieve (p:ps) = p : sieve [x | x <- ps, x `mod` p > 0]

primeFactors :: Integer -> [Integer]
primeFactors n = takeWhile (< n) [x | x <- primes, n `mod` x == 0]

这是我的代码.我想你猜对了我要做的事情:使用无限素数列表给定数字的素数因子列表.但是这段代码不会懒惰地评估.

当我使用ghci和:l mycode.hs输入时primeFactors 24,结果是[2, 3(并且光标在那里不断闪烁)没有进一步的Prelude>提示.我认为那里有一个问题.我究竟做错了什么？

谢谢.

我正在努力解决欧拉项目3:

Description: The prime factors of 13195 are 5, 7, 13 and 29.
             What is the largest prime factor of the number 600851475143 ?

这是我生成答案的代码.但是我需要一个整数类型来保存600851475143.当我在Mac上的GCC上编译它时,我得到:

integer constant is too large for ‘long’ type". 

我希望很久很久就可以很容易地掌握这个数字 我也试过让它没有签名.为什么我的代码不能容纳那么少的数字,我该怎么做才能使它工作？

#include <iostream>
#include <vector>

using namespace std;

static bool IsPrimeFactor(int numToTest,int testNum,vector<int> factors)
{
    if(numToTest%testNum==0) // is it a factor?
    {
        // see if it is a prime factor
        for(unsigned int i=0; i < factors.size(); i++)
        {
            if(testNum%factors[i]==0)  // see if this factor …

我很清楚函数原型,这个错误似乎是一个函数声明错误,这意味着我真的很困惑,为什么我看到这个警告,从而错误.

这几乎就像gcc完全忽略了我的函数原型.这是编译器错误吗？

为了简洁起见,我没有在单独的头文件中声明此函数,尽管它应该没有区别.

gcc输出:

$ gcc -Wall -std=c99 -pedantic primefactors.c
primefactors.c: In function ‘main’:
primefactors.c:8:5: warning: implicit declaration of function ‘largestprime’ [-Wimplicit-function-declaration]
primefactors.c: At top level:
primefactors.c:12:6: error: conflicting types for ‘largestprime’
primefactors.c:8:20: note: previous implicit declaration of ‘largestprime’ was here

码:

#include <stdio.h>
#include <math.h>

long largetsprime(long);

int main()
{
    printf("%d\n", largestprime(600851475143));
    return 0;
}

long largestprime(long num)
{
    int highest;
    int mid = sqrt(num);
    for (int i = 2; i < mid; i++) {
        if (mid % i …

我已经开始解决 Rust 中的 Project Euler 问题，并遇到了#3，其中最简单的快速方法是实现埃拉托色尼筛法。

在此过程中，我的算法创建了一个迭代器，然后过滤掉非素数并将其分配回原始向量，但我收到了Vec<u32>无法从 构建的错误Iterator<Item=&u32>。

代码：

fn eratosthenes_sieve(limit: u32) -> Vec<u32> {
    let mut primes: Vec<u32> = Vec::new();
    let mut range: Vec<u32> = (2..=limit).collect();
    let mut length = range.len();

    loop {
        let p = range[0];
        primes.push(p);

        range = range.iter().filter(|&n| *n % p != 0).collect();

        if length == range.len() {
            break;
        }
        length = range.len();
    }

    primes
}

错误：

fn eratosthenes_sieve(limit: u32) -> Vec<u32> {
    let mut primes: Vec<u32> = …