5

我正在尝试制作一个程序来评估 3 个数字（基数）的 gcd，如果base1and base2、base2andbase3和base3and的 GCDbase1都等于 1，则将基数评估为一个范围内的指数。基本上，我需要做的是弄清楚他们的 GCD 是否等于 1，然后计算数字的幂。这是它的样子：

bases = 150
powers = 150
base1 = all numbers 1-bases
base2 = all numbers 1-bases
base3 = all numbers 1-bases
if the GCD of all combinations = 1
    do base1^all numbers 3-powers
    do base2^all numbers 3-powers
    do base2^all numbers 3-powers
    then store all of those in an array

现在，我尝试使用可怕的for循环，但它非常慢，我不认为它是一个解决方案。只有当基地和权力是 10 或以下时，它才能快速工作。我怎么能不使用for循环来做到这一点？或者，如果我必须使用for循环，我怎样才能减少使用的数量？我可以计算出 3 个 GCD 组合等于 1 的数字吗？for我尝试过的循环如下：

for i = 1:numbers
    for j = 1:numbers
        for k = 1:numbers
            if gcd(i,j) == 1 && gcd(i,k) == 1 && gcd(k,j) == 1
                for a = 3:powers
                    for b = 3:powers
                        for c = 3: powers
                            x = i^a
                            y = j^b
                            z = k^c
                        end
                    end
                end
            end
        end
    end
end
4

2 回答 2

3

我认为这个问题可以通过矢量化方式解决，如下所示

%Generate all possible triplets.
[x1,x2,x3]=ndgrid(1:3,1:3,1:3);
v=[x1(:) x2(:) x3(:)];

现在定义一个匿名函数。

gcd3_test=@(a,b,c)(gcd(a,b)==1 & gcd(b,c)==1 & gcd(a,c)==1)
gcdTest=gcd3_test(v(:,1),v(:,2),v(:,3));
v=v(gcdTest,:);

同样地为你所有的力量生成三元组。

[x1,x2,x3]=ndgrid(3:10,3:10,3:10);
p=[x1(:) x2(:) x3(:)];

然后我猜你将不得不使用 for 循环（但只有一个）：

重要提示：我假设如果您for为 powers 运行循环3:150，并且您需要存储所有x,y,z内容，那么您将需要大量内存（35034 GB，即使是单精度）。你没有在你的代码中这样做。

所以不要尝试下面的 for 循环。

%DO NOT RUN
for i=1:size(v,1)
    vReplicated=repmat(v(i,:),size(p,1),1);
    v_RaisedTo_P{i}=vReplicated.^p;
end

注意：请注意，在进行 GCD 测试时您不关心顺序（即您的if条件。所以我认为您可以过滤掉很多三元组，但这会影响您的功率计算。

allTriplets=sort(allTriplets,2);
allTriplets=unique(allTriplets,'rows'); %27 triplets reduce to 10
于 2013-12-11T04:15:11.037 回答
0

该代码表明您已经实现了两个整数的 gcd 或者您使用内置？gcd(a,b,c) 等于 gcd(a,gcd(b,c))

gcd3=@(a,b,c)(gcd(a,gcd(b,c)))
于 2013-12-10T22:20:30.947 回答