我正在尝试测试以下因子分解函数,但它正在为大量素数爆发:
(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 …我是编程的新手,我的一个朋友建议我应该对Euler项目进行练习以使其更好.我在问题3上遇到了问题:
"13195的主要因素是5,7,13和29. 600851475143中最大的主要因素是什么？"
现在这是我的解决方案:
class Program
{
static void Main(string[] args)
{
long number = 600851475143;
bool prime = true;
for (long i = 3; i <= number; i++)
{
for (long n = 2; n < i; n++)
{
if (i % n == 0)
{
prime = false;
break;
}
}
if (prime)
{
if (number % i == 0)
{
Console.WriteLine(i);
}
}
prime = true;
}
Console.ReadKey();
}
}
现在,虽然我确实得到了正确的答案(这是6857),但我发现我的方法非常低效.如果您将运行我的代码,您将看到它仍将在超过2分钟之后运行...我的问题是如何为此编写更高效/更快的代码？
每当我使用Pollard Rho分解方法对数字进行因子分解时,是否有必要在Pollard Rho分解之前检查它的素数？如果是,那么我必须实施Miller Rabin的素性测试或任何素性测试,每次我想要考虑任何数字而且我必须要处理强伪赝,这不是很复杂吗？有没有简单而又更快的方法来处理这个问题？(我在最多10位数的数字上使用这些测试)
我一直想学习Haskell,所以最近我开始解决ProjectEuler问题.在编写以下分解代码时,我注意到调用(/ n)返回一段Float时间后(n `div`)返回一个Int.我认为中缀符号只是Haskell中的语法糖？有人可以解释发生了什么吗？我还要感谢任何意见/建议/改进,谢谢.
import Data.List (sort)
factor :: Int -> [Int]
factor 0 = [1..]
factor n =
let f1 = [f | f <- [1..limit], n `mod` f == 0]
where limit = ceiling $ sqrt $ fromIntegral n
f2 = map (n `div`) f1 --vs. map (/ n) f1
in sort $ f1 ++ f2
def test_prime(n):
q = True
for p in range(2,n): #Only need to check up to rootn for primes and n/2 for factors
if int(n%p) is 0:
q = False
print(p, 'and', int(n/p), 'are factors of ', n)
if q:
print(n, 'IS a prime number!')
else:
print(n, 'IS NOT a prime number')
我刚刚开始使用Python,我正在整理一些零碎的东西来消磨时间.我一直在玩质数测试,并有想法显示非素数的因素.我上面列出的函数似乎运行得很好,除了输出不一致.
例如,如果我设置n = 65432我得到...
2 and 32716 are factors of 65432
4 and 16358 are factors of 65432
8 and 8179 are factors of 65432
8179 and 8 are …我正试图从http://projecteuler.net解决问题3 .但是,当我运行程序时,没有打印出来.我究竟做错了什么？问题:600851475143的最大主要因素是什么？
public class project_3
{
public boolean prime(long x) // if x is prime return true
{
boolean bool = false;
for(long count=1L; count<x; count++)
{
if( x%count==0 )
{
bool = false;
break;
}
else { bool = true; }
}
return bool;
}
public static void main(String[] args)
{
long ultprime = 0L; // largest prime value
project_3 object = new project_3();
for(long x=1L; x <= 600851475143L; x++)
{
if( object.prime(x)==true )
{
ultprime = …每当我尝试解决一些数学问题,比如找到一定数量因素的特定产品,我就用Python做
for x in xrange(1,10):
for y in xrange(1,10):
for z in xrange(1,10):
product = x * y * z
if product == 36:
print "factors : {0},{1},{2}".format(x,y,z)
在这个例子中,它非常简单并快速完成工作,但我想知道你们是否知道更简单或更简单的方法来编写它.关于如何做到这一点的任何想法,而不是使用那么多迭代或反复重复几乎相同的代码.这显然是有3个因素,但我添加的因素越多,代码越长,重复性越高.关于如何简化这类简单问题的代码的任何想法？谢谢
我正在尝试编写一个算法,该算法可以返回小于实例n的正整数集,并且可以将其分解为2 ^ p5 ^ q.我的数学不是最好的,所以我不知道如何确定一个数字是否可以用这种特定的形式分解...
任何帮助将非常感激 :)
给定一个数字1 <= n <= 10^18，我如何将其最小化时间复杂度？
互联网上有很多帖子介绍如何找到主要因素，但是在特定情况下，它们都（至少从我所看到的情况）没有陈述它们的好处。
除了Eratosthenes的筛子之外，我还使用Pollard的rho算法：
n尽可能除以这些质数。我的实现：
#include <iostream>
#include <vector>
#include <cstdio>
#include <ctime>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
using namespace std;
typedef unsigned long long ull;
typedef long double ld;
typedef pair <ull, int> pui;
#define x first
#define y second
#define mp make_pair
bool prime[10000005];
vector <ull> p;
void initprime(){
prime[2] = 1;
for(int i = 3 ; i < 10000005 ; i += 2){ …algorithm primes sieve-of-eratosthenes prime-factoring factorization