Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
Ballin primality test
Language:
Ada
Assembly
Bash
C#
C++ (gcc)
C++ (clang)
C++ (vc++)
C (gcc)
C (clang)
C (vc)
Client Side
Clojure
Common Lisp
D
Elixir
Erlang
F#
Fortran
Go
Haskell
Java
Javascript
Kotlin
Lua
MySql
Node.js
Ocaml
Octave
Objective-C
Oracle
Pascal
Perl
Php
PostgreSQL
Prolog
Python
Python 3
R
Rust
Ruby
Scala
Scheme
Sql Server
Swift
Tcl
Visual Basic
Layout:
Vertical
Horizontal
//g++ 5.4.0 Primality test Ballin primality test #include <bits/stdc++.h> using namespace std; typedef uint64_t ui; ui binPower(ui a, ui b , ui p){ ui res = 1; a = a%p; while(b>0){ if(b&1) res = (res * a) %p; a = a*a%p; b>>=1; } return res%p; } bool checkComp(ui n , ui a , int d, int s){ int status = binPower(a,n-1,n); if(status==1 || status == n-1) return false; for(int r=0;r<s;r++){ a = (a*a)%n; if(a==n-1) return false; } return true; } bool checkComposite(ui n){ if (n < 4) return n == 2 || n == 3; ui d = n-1; int s = 0; while(d&1==0){ d>>=1; s++; } for(ui a=0;a<10;a++){ if(checkComp(n,a,d,s)==false){ return false; } } return true; } int main() { if(checkComposite(28)) cout<<"No"; else cout<<"Yes"; return 0; }
g++
Show compiler warnings
[
+
] Compiler args
[
+
]
Show input
Compilation time: 1.43 sec, absolute running time: 0.08 sec, cpu time: 0.02 sec, memory peak: 3 Mb, absolute service time: 1,54 sec
edit mode
|
history
|
discussion
Yes