Is a Recursive-Iterative Method Better than a Purely Iterative Method to find out if a number is prime?

by

Since your program tests just one number, you’re wasting time trying to avoid testing by composites. You perform a lot of computations to save one meager modulo operation.

If you were testing more than a few numbers in a row for primality, then it would make sense to pre-compute the primes up to a sqrt of the top limit of that range, and go through those primes when testing the candidates.

Better yet will be to perform an offset sieve of Eratosthenes (C code here), to find the primes in a given range. The time complexity of the sieve of Eratosthenes to find primes from 2 to N is O(N log log N); and trial division by primes up to the sqrt, O(N^1.5 / (log N)^2) (which is worse; e.g. the ratio of run times for the sieve up to 1mln compared to 100k is 10.7x, vs 22x for trial division; 2mln vs 1 mln is 2.04x for the sieve, 2.7x for the trial division).

Pseudocode for the offset sieve of Eratosthenes:

Input: two Integers n >= m > 1

Let k = Floor(Sqrt(n)),
Let A be an array of Boolean values, indexed by Integers 2 to k, and
    B an array of Booleans indexed by Integers from m to n,
    initially all set to True.

for i = 2, 3, 4, ..., not exceeding k:
  if A[i] is True:
    for j = i^2, i^2+i, i^2+2i, ..., not greater than k:
      A[j] := False
    for j = i^2, i^2+i, i^2+2i, ..., between m and n, inclusive:
      B[j] := False

Output: all `i`s such that B[i] is True, are all the primes 
                                     between m and n, inclusive.

A common optimization is to work with odds only, i = 3,5,7,..., avoiding any even numbers from the outset (2 is known to be a prime anyway, and any even number is a composite). Then the step of 2i, and not just i, can be used in both inner loops. Thus the even indices are excluded from processing altogether (usually with condensed addressing schemes, val = start + 2*i).

More Related Contents:

  1. Recursive C function
  2. optimized sum of an array of doubles in C [duplicate]
  3. can anyone explain the output of the following code in c [closed]
  4. Improve INSERT-per-second performance of SQLite
  5. Is recursion ever faster than looping?
  6. Trying to understand gcc option -fomit-frame-pointer
  7. Why is this code using strlen heavily 6.5x slower with GCC optimizations enabled?
  8. How Recursion works in C
  9. Matrix multiplication: Small difference in matrix size, large difference in timings
  10. Is it faster to count down than it is to count up?
  11. What is the fastest way to swap values in C?
  12. Efficiency: arrays vs pointers
  13. Enumerate factors of a number directly in ascending order without sorting?
  14. Efficient 4×4 matrix vector multiplication with SSE: horizontal add and dot product – what’s the point?
  15. No performance gain after using openMP on a program optimize for sequential running
  16. How to work on a sub-matrix in a matrix by pointer?
  17. When is assembly faster than C? [closed]
  18. Linked list recursive reverse
  19. AVX/SSE version of xorshift128+
  20. Best timing method in C?
  21. How does the CPU cache affect the performance of a C program
  22. why does GCC __builtin_prefetch not improve performance?
  23. Concatenating strings in C, which method is more efficient?
  24. Faster approach to checking for an all-zero buffer in C?
  25. Values obtained in case of a recursive function
  26. Inline function v. Macro in C — What’s the Overhead (Memory/Speed)?
  27. Is x += 1 more efficient than x = x + 1?
  28. Iterating over same type struct members in C
  29. Why vectorizing the loop over 64-bit elements does not have performance improvement over large buffers?
  30. Infinite recursion in C

Leave a Comment