Primality Testing

#1

All the test cases are giving the correct output except for the 1st one… please can you tell me the mistake in the code.

#2

I’ll suggest you do rewrite code and put this within single function with this pseudocode:

function: MillerRabin_PrimalityTesting(int N):
    if N%2 = 0:
        return composite

    write N-1 as (2^R . D) where D is odd number
    pick a random integer k     //not too less. not too high.

    LOOP: repeat k times:
        pick a random integer A in range [2,N-2]
        X = A^D % N
        if X = 1 or X = N-1:
            continue LOOP
        for i from 1 to r-1:
            X = X^2 % N
            if X = 1:
                return composite
            if X = N-1:
                continue LOOP
        return composite
    return probably prime
#3

this is valid for N>2

#4

I have made a single function but now also 1st case is failing…

#5

I manually checked your code on first input and it showed correct answer, there might be some problem at backend.

1 Like