 #1
zak100
 462
 11
 TL;DR Summary

From the internet, I found that the running time of algorithm to find prime number is O(sqrt(N)).
I have 3 questions: Can we say that the running time is O(log^2N) for detection of Prime number? For large values of N, can we say that its a pseudopolynomial algorithm? Is this true for Sorting algorithms also?
Zulfi.
Hi,
I want to know if the algorithm to find prime number has running time O(sqrt(N)) or O(log^2N). log^2N is better than sqrt(N). Also for large values can it become a pseudo polynomial algorithm?
Zulfi.
I want to know if the algorithm to find prime number has running time O(sqrt(N)) or O(log^2N). log^2N is better than sqrt(N). Also for large values can it become a pseudo polynomial algorithm?
Zulfi.