Why do we check up to the square root of a number to determine if the number is prime?

by

If a number n is not a prime, it can be factored into two factors a and b:

n = a * b

Now a and b can’t be both greater than the square root of n, since then the product a * b would be greater than sqrt(n) * sqrt(n) = n. So in any factorization of n, at least one of the factors must be smaller than the square root of n, and if we can’t find any factors less than or equal to the square root, n must be a prime.

More Related Contents:

  1. How to find nth prime with complexity o(1)
  2. How to create the most compact mapping n → isprime(n) up to a limit N?
  3. How to create the most compact mapping n → isprime(n) up to a limit N?
  4. Segmented Sieve of Eratosthenes?
  5. nᵗʰ ugly number
  6. Generate a list of primes up to a certain number
  7. Fastest primality test
  8. The Sieve of Atkin
  9. Generating integers in ascending order using a set of prime numbers
  10. Find prime numbers using Scala. Help me to improve
  11. Given Prime Number N, Compute the Next Prime?
  12. Calculating phi(k) for 1
  13. Reason for the number 5381 in the DJB hash function?
  14. How to convert floats to human-readable fractions?
  15. Subset Sum algorithm
  16. How to calculate an angle from three points? [closed]
  17. Which sort algorithm works best on mostly sorted data? [closed]
  18. Linear time algorithm for 2-SUM
  19. Which parallel sorting algorithm has the best average case performance?
  20. finding if two words are anagrams of each other
  21. Create a random permutation of 1..N in constant space
  22. O(klogk) time algorithm to find kth smallest element from a binary heap
  23. Calculating permutations in F#
  24. RGB value base color name
  25. Print the biggest K elements in a given heap in O(K*log(K))?
  26. Variation on knapsack – minimum total value exceeding ‘W’
  27. Path generation for non-intersecting disc movement on a plane
  28. How can I perform Collision Detection on rotated rectangles? [closed]
  29. algorithm to check a connect four field
  30. What is the most efficient way to encode an arbitrary GUID into readable ASCII (33-127)?

Leave a Comment