标签: modular-arithmetic

我试图在一台机器上计算素数,大小约为2 ^ 30-2 ^ 100.
对于任何感兴趣的人,我的算法都包含在
我已经针对O(sqrt(n/2))每个数字优化了这个Python代码(我相信):它只接受奇数,并且我确保传递给它的数字在另一个方法中是奇数.

我使用费马素性测试来尝试加快这个过程.但是,对于内置math.pow()方法,数字太大,所以我使用了Squaring的Exponentiation.
然而,对于更大的数字来说这需要很长时间 - 使用蛮力会更快.

我的实施错了吗？
时间来自平方算法,它的重复堆栈也占用了我的记忆,我应该研究一个更快的算法吗？

要计算数字35184372088967是否为素数,使用我的强力算法需要.00100111秒,但需要.40608秒来运行素数测试.

蛮力素数检查:

def isPrime(n):
    for i in range(3,int(math.sqrt(n)),2):
        if(n%i==0):
            return False
    return True

Fermat算法的实现:

def couldBePrime(n):
        if(n>308):
            return power(2,n-1)%n==1
        else:
            return math.pow(2,n-1)%n==1

通过平方算法的指数化(耗时部分):

def power(base,exp):
    if exp == 0:
        return 1
    elif exp == 1:
        return base
    elif (exp & 1) != 0:
        return base * power(base * base, exp // 2)
    else:
        return power(base * base, exp // 2)

我正在做一些纠错，我需要在Java的mod 11下将两位数字相除。

现在，我知道了，通过使用模块化计算器：

9/1 mod 11 = 9
2/10 mod 11 = 9

问题出在让Java计算这一点。在Java中：

(9 / 1) % 11 = 9 - This is fine
(2 / 10) % 11 = 0 - This is not correct.

我知道Java在技术上不能执行模块化操作，而我的一部分则在想我要么需要以某种方式计算逆，要么使用数组来存储可能的输出值。

假设我尝试执行以下操作:

y = 0;
z = x % y;

是这个明确定义,平台相关或未定义的语义？我主要是关于C/C++的问题,但我对各种编程/脚本语言(Java,perl,sh等)的答案感兴趣

我问的部分是因为有不同的 可能方法来定义模运算:作为除法运算的剩余部分 ; 作为商群的大小等

例如,我有一个参考编号a = 15和b= 3.

• 如果x=2,f(a,b,x) = 1因为如果将15分成3部分,则数字2在第一部分中.
• 如果x=7,f(a,b,x) = 2因为如果将15分成3部分,则数字7在第二部分中.
• 如果x=15,f(a,b,x) = 3因为如果将15分成3部分,则数字15在第3部分中.
• 如果x <0或> 15,结果与我无关.

有这样的内置功能吗？

任何人都可以解释为什么会发生这种情况吗？:

int a = 2147483647;
cout <<"Product = " << a * a << endl; // output = 1 (why?)
int b = -2147483648;
cout <<"Product = " << b * b << endl; // output = 0 (why?)

此外，当我们为 'short' 编写类似的内容时，编译器将乘积视为整数类型，尽管变量被初始化为短类型，例如：

short x = 32767;
cout <<"Product = " << x * x << endl; // Product = 1073676289
short y = -32768;
cout <<"Product = " << y * y << endl;// Product = 1073741824