May 2021
1 / 4
May 2021
May 2021
rogergao
May '21

link to the code6

This is the code I’ve written for the Miller-Rabin, due to the fact that I want to keep the code short, I used __int128(defined in the code to be extra_long), after passing test cases on an online judge in my
home country, I submitted it to SPOJ and got WA.

I changed my code many times and even used a program to compare my results with the results of an AC code, but cannot find any difference.

If anyone can find the data my program failed, I will be giving my thanks!

  • created

    May '21

  • last reply

    May '21
  • 3

    replies

  • 674

    views

  • 3

    users

  • 1

    link

simes
May '21

I couldn’t find any test case where your code gave the wrong answer.

(But, seeding the random number generator with the current time makes every run unrepeatable anyway, so even if I did find a failure, there’s no guarantee you’d be able to repeat it.)

rogergao
May '21

Thanks, my friend has found an number 6601 that my program can’t run correctly, now i am fixing it.

luckymastermin
May '21

I was just doing trial and error and it seems this problem have very very weak test case. below 3 lines of python code can get AC`

import sys
a=int(input())
for p in sys.stdin:
	s=int(p);
	if(pow(2,s-1,s)>1 or pow(3,s-1,s)>1 or s==1):
		print("NO")
	else:
		print("YES")`