Choosing the Optimal Algorithm in PHP

Sometimes a code problem can be related to the fact that the chosen solution is not the most optimal one.

Suppose, for example, we are faced with the task of finding the sum of integers from 1 to 1000000. Let's solve the given problem:

<?php
	$sum = 0;
	
	for ($i = 1; $i <= 1000000; $i++) {
		$sum += $i;
	}
	
	echo $i;
?>

So what's wrong? The fact is that for solving this problem, there is a mathematical solution.

This solution requires almost no resources! Let's program it:

<?php
	$n = 1000000;
	$sum = $n * ($n + 1) / 2;
	echo $sum;
?>

Moral: before solving a resource-intensive task, always check if there is a ready-made mathematical formula or a ready-made mathematical approach for its solution.

Find the number of numbers divisible without a remainder by 5, in the range from 1 to 1000.

Find the number of digits that will be needed to write all numbers from 1 to 1000000.

Find all prime numbers in the range from 1 to 10000. This is a bonus task, you can skip it.