1

I am working on a program in which I have calculated a number of type long after applying some calculations according to my algorithm. Now, I have to find a relative prime to this number that I have generated. How can I do this? I know that if two numbers are relative prime then their GCD == 1 but in this case I don't have another number. I have only one number which is getting generated in my program and I need to calculate a relative prime number for this number.

Edit

Condition for generating relative prime is such that:

1 < relative prime < generated Number

Any help is appreciated.

4

1 回答 1

5

获得相对质数的简单方法：

现在，我必须找到这个数字的相对质数

对于整数n，n>2它总是正确的n并且n-1是相对质数。所以假设n不是 2 或更少，只是有n-1输出，因为它保证相对质数。如果n等于 2，那么您的条件是不可能的。

非平凡的相对素数

如果您想要一个重要的解决方案，您总是可以实际计算 GCD。使用 Euclid 方法如下：

long findGCD(long l1, long l2) {
    //end recursion
    if(l2 == 0){
        return number1;
    }
    return findGCD(l2, l1%l2);
}

并使用 while 循环尝试从 开始的所有数字，n+2直到 GCD 为 1。

于 2013-10-11T23:34:15.907 回答