Loops That Search and Loops That Converge

Week 9 has two halves. The first is prime numbers: testing one number, then finding every prime in a range, which nests the test inside a second loop. The second is the Taylor series for cosine and sine, summed to N terms and compared with the answer from <math.h>, which is the syllabus's "with and without the in-built function". The primes are chapter 6 with a break; the series are chapter 3's floating-point arithmetic driven by a loop, and they teach the one trick that separates a series program that works from one that overflows: build each term from the one before it.

Program 1: Is a Number Prime?

A prime has exactly two divisors, 1 and itself. Numbers below 2 are not prime by definition, and any other number is prime unless some integer from 2 upward divides it.

Algorithm:

  1. Start.
  2. Read n.
  3. Assume n is prime; if n is below 2, it is not.
  4. For each i from 2 while i × i ≤ n: if i divides n, n is not prime; stop looking.
  5. Print the verdict.
  6. Stop.

17 is prime, 18 is not, and 1 is not. The flag prime starts at 1, meaning "no divisor found yet", and the first divisor flips it to 0 and leaves the loop with break; a prime is a number that survives the whole loop with the flag intact.

The loop bound is the part to understand rather than copy. Divisors come in pairs, one at most √n and its partner at least √n, so if nothing up to √n divides n, nothing does, and the search can stop there: 17 needs only 2, 3, and 4 tried. The textbook writes that bound as i * i <= n, and for the numbers in a textbook that works. For n near the top of the int range it does not: i * i passes 2 billion when i reaches 46341, and signed overflow is undefined behaviour, so the loop that tests whether 2147483647 is prime is not a C program at all. i <= n / i says the same thing with a division that cannot overflow, and this program answers 2147483647 is prime, which it is, after about forty-six thousand iterations that take a few milliseconds. Try it.

Program 2: All the Primes Between N1 and N2

Algorithm:

  1. Start.
  2. Read n1 and n2; if n1 > n2, or n2 is above 1000000, print a message and stop.
  3. For each n from n1 to n2: if n ≥ 2, test it with program 1's loop; if it is prime, print it.
  4. If no prime was printed, say so.
  5. Stop.

10 30 prints primes between 10 and 30: 11 13 17 19 23 29, and 24 28 reports that there are none. The inner loop is program 1 unchanged; the outer loop runs it once per candidate, which is why prime is reset to 1 at the top of every outer pass, the same reset week 8's digit sum needed. The break only leaves the inner loop, so the outer one carries on to the next candidate, which is exactly the behaviour wanted here and the thing to know about break in nested loops.

The output is arranged so that a heading is printed with the first prime and later primes get a space in front, and the count decides at the end whether to close the line or report an empty range. The cap on n2 keeps the run inside the sandbox's time limit; trial division up to a million takes well under a second, and the lesson on why that gets slow for larger ranges belongs to a later course.

Program 3: cos(x) from Its Series

cos x = 1 − x²/2! + x⁴/4! − x⁶/6! + ... The lab asks for the sum of the first N terms and, alongside it, the library's answer.

Algorithm:

  1. Start.
  2. Read x in radians and the number of terms N; if N is below 1 or above 100, print a message and stop.
  3. Set term to 1 and sum to 0.
  4. Repeat N times, with k from 0: add term to sum, then set term to −term × x² / ((2k + 1)(2k + 2)).
  5. Print sum and the library cos(x).
  6. Stop.

1.0 10 gives 0.540302 on both lines. Now try 2 3: three terms of the series give -0.333333 against the library's -0.416147, and 2 10 closes the gap. That is what "up to N terms accuracy" means, and printing the two side by side is the demonstration.

The recurrence on step 4 is the technique of the week. Each term of the series is the previous term multiplied by −x² and divided by the next two integers: from x⁴/4! to x⁶/6! is a factor of −x²/(5 × 6). So the program never computes a power or a factorial. The obvious alternative, pow(x, 2 * k) / factorial(2 * k) for each term, fails twice over: 20! is already past the range of a 32-bit long, so the factorial overflows, and even in double the power and factorial each grow enormous before their quotient shrinks, which throws away precision. The recurrence keeps every intermediate value the size of a term. The sign alternates because the factor is negative, so no separate sign variable is needed.

Program 4: sin(x) from Its Series

sin x = x − x³/3! + x⁵/5! − x⁷/7! + ... The same program with a different first term and a different pair of integers in the recurrence.

Algorithm:

  1. Start.
  2. Read x in radians and N; if N is below 1 or above 100, print a message and stop.
  3. Set term to x and sum to 0.
  4. Repeat N times, with k from 0: add term to sum, then set term to −term × x² / ((2k + 2)(2k + 3)).
  5. Print sum and the library sin(x).
  6. Stop.

1.0 10 gives 0.841471 twice, and 2 2 gives the two-term estimate 0.666667 against 0.909297. From x³/3! to x⁵/5! the factor is −x²/(4 × 5), which is where (2k + 2)(2k + 3) comes from with k starting at 0, and the first term is x itself rather than 1.

Both series take x in radians, because that is what the mathematics and the library assume. A student who types 90 100 expecting sin of ninety degrees gets sin of ninety radians, about 0.894, from the library line, and a number in the region of 10²¹ from the series line. For x = 90 the terms grow to around 10³⁷ before they start shrinking, and a double that sums values that size loses every digit of the answer to cancellation, however many terms it is allowed. The series is only usable for small x. Convert degrees with x × π / 180 before the loop, or reduce a large angle by multiples of 2π first: 1.5708 10 is ninety degrees, and both lines agree on it. And both programs cap N at 100 for tidiness rather than safety: past a couple of dozen terms the recurrence is adding numbers too small to change a double, and the series has converged as far as it ever will.

Key Takeaways

  • A number is prime if no integer from 2 to √n divides it; a flag set to 1 and cleared by the first divisor, with break, is the loop.
  • Write the bound as i <= n / i, not i * i <= n: the multiplication overflows for large n and signed overflow is undefined behaviour.
  • To test a range, nest the prime loop inside a loop over candidates, reset the flag every pass, and remember that break leaves only the inner loop.
  • Sum a series by building each term from the previous one; never compute powers and factorials separately, which overflow and lose precision.
  • cos: term starts at 1, factor −x²/((2k+1)(2k+2)). sin: term starts at x, factor −x²/((2k+2)(2k+3)).
  • x is in radians for both the series and the library; print the two side by side to show N-term accuracy.