这是一个问题:
"编写一个名为gcd的方法,它接受两个整数作为参数,并返回两个数字的最大公约数.两个整数a和b的最大公约数(GCD)是a和b两者的最大整数.任何数字和1的GCD是1,任何数字的GCD和0都是该数字.
计算两个数字的GCD的一种有效方法是使用Euclid算法,该算法表明以下内容:
GCD(A, B) = GCD(B, A % B)
GCD(A, 0) = Absolute value of A"
我真的很困惑如何解决这个问题.我只想提供一些提示和提示,告诉我到目前为止我在程序中做错了什么.(我必须放入扫描仪,这是我老师的要求.)不要给我一个完整的代码,因为我有点想自己解决这个问题.也许只是给我一个暗示我如何结合你在上面看到的这个公式.(如果你想知道为什么我输入== 0,那是因为我认为如果你有两个数字,比如0和90,他们的GCD会是0吗？)
此外,我的代码必须包括while循环......如果循环我会更喜欢...
提前致谢!:)
我目前的计划:
public static void main(String[] args) {
Scanner console = new Scanner(System.in);
int a = console.nextInt();
int b = console.nextInt();
gcd (a, b);
}
public static void gcd(int a, int b) {
System.out.print("Type in two numbers and I will print outs its Greatest Common Divisor: ");
int gcdNum1 = console.nextInt();
int gcdNum2 = console.nextInt();
while (gcdNum1 == 0) { …我正在使用Python v3.1中的分数模块来计算最大的公约数.我想知道使用什么算法.我猜测欧几里德方法,但我想确定.文档(http://docs.python.org/py3k/library/fractions.html?highlight=fractions.gcd#fractions.gcd)没有帮助.有人能告诉我吗？
我刚刚发现这个算法来计算我的讲义中最大的公约数:
public static int gcd( int a, int b ) {
while (b != 0) {
final int r = a % b;
a = b;
b = r;
}
return a;
}
所以r是将b分成a(得到mod)时的余数.然后b被分配给一个,其余被分配给b,和一个被返回.我不能为我的生活看到它如何运作!
然后,显然这个算法不适用于所有情况,然后必须使用这个:
public static int gcd( int a, int b ) {
final int gcd;
if (b != 0) {
final int q = a / b;
final int r = a % …一种方法是计算他们的gcd并检查它是否为1.
有更快的方法吗？
是否numpy有一个gcd功能都在其模块的结构？
我知道fractions.gcd但是认为numpy等效可能更快,并且使用numpy数据类型可以更好地工作.
我一直无法在谷歌上发现任何东西,除了这个看起来过时的链接,我不知道我将如何访问_gcd它建议存在的功能.
天真的尝试:
np.gcd
np.euclid
对我不起作用......
clang 和 GCC 有一个int __builtin_ctz(unsigned)功能。这会计算整数中的尾随零。关于这一系列函数的维基百科文章提到可以使用 加速二进制 GCD 算法__builtin_ctz，但我不明白如何。
二进制 GCD的示例实现如下所示：
unsigned int gcd(unsigned int u, unsigned int v)
{
// simple cases (termination)
if (u == v)
return u;
if (u == 0)
return v;
if (v == 0)
return u;
// look for factors of 2
if (~u & 1) // u is even
if (v & 1) // v is odd
return gcd(u >> 1, v);
else // …c++ algorithm bit-manipulation built-in greatest-common-divisor
我想在我的应用程序中简化一小部分.分数类似于x/y,其中x和y是整数.我想将分数简化为最简单的形式.任何人都可以给我提示如何做到这一点.提前致谢.
我已经有一个找到2个数字的GCD的函数.
function getGCDBetween($a, $b)
{
while ($b != 0)
{
$m = $a % $b;
$a = $b;
$b = $m;
}
return $a;
}
但现在,我想扩展此功能以找到N点的GCD.有什么建议吗？
我正在尝试使用java.math.BigInteger进行一些精确的整数矩阵计算,其中标量值达到数百万位.我注意到一些内置的BigInteger操作出乎意料地非常慢 - 特别是gcd的一些情况,以及更多modInverse的情况.看来我可以更快地实现我自己的这些函数版本.
我写了一个程序打印计算gcd(10 ^ n-3,10 ^ n)的时间,用于增加n的值达到一百万左右,使用内置gcd或我自己的简单替代实现:
private static java.math.BigInteger myGcd(java.math.BigInteger a, java.math.BigInteger b)
{
a = a.abs();
b = b.abs();
while (true)
{
if (b.signum() == 0) return a;
a = a.mod(b);
if (a.signum() == 0) return b;
b = b.mod(a);
}
} // myGcd
我在ubuntu linux下使用java 8运行它,运行时版本为1.8.0_111-8u111-b14-2ubuntu0.16.04.2-b14.在Java运行时1.8.0_92的macbook上,时间相对大致相似.
内置gcd大致是二次方的:
# numDigits seconds
1 0.000005626
2 0.000008172
4 0.000002852
8 0.000003097
16 0.000019158
32 0.000026365
64 0.000058330
128 0.000488692
256 0.000148674
512 0.007579581
1024 0.001199623
2048 0.001296036
4096 0.021341193 …def gcd(e, z):
if z == 0:
return e
else:
return gcd(z, e % z)
e = int(input("Please enter the first number:"))
z = int(input("Please enter the second number:"))
print ("The GCD of ",e," and ",z," is ",gcd(e,z))
d = 1
while d < e:
if d * e == 1 % z:
print (d," * ",e," = 1 (mod ",z,")")
d = d + 1
else:
d = d + 1
我试图使用这个代码通过蛮力找到rsa的候选人,它似乎应该工作,但它不能任何人帮助我吗？
z =(p - 1)(q - 1)用于计算z之前使用p = …