Hola,

De dónde sale esa i?

is_prime = i%j != 0;

Saludos!

Bueno, quizá sea el más eficiente desde la fuerza bruta, porque el más eficiente es la "criba general del cuerpo de números".
Por otro lado, veo un pequeño problema en la parte de la presentación, por lo menos usa paréntesis para que quede más claro todo, en lugar de:
Podrías poner

Luego, siempre me ha hecho gracia usar los operadores "==" y "!=" fuera de un if o for, sin embargo hay que reconocer que es poco comprensible, y al final se supone que perseguimos la legibilidad del código. Si usaras
apenas se traduce en cuatro instrucciones más en ensamblador, no se pierde en eficiencia y se gana en legibilidad.

De todas formas, yo creo que puede hacerse más simple sin perder eficiencia.

En cuanto a tu duda original, cuando se busca saber si un número es primo no tiene sentido buscar divisores mayores a la raiz cuadrada del número.
El motivo de esto es el siguiente:

Supongamos que quiero saber si n es un número primo.
Lo que voy a hacer será empezar a probar por j=2 si el resto de dividir n por 2 es 0 y así iterando en j.
Ahora, consideremos lo que ocurre cuando j=parte_entera(raiz_cuadrada(n))+C (C siendo una constante entera positiva cualquiera).
Para que j sea divisor de n, debe existir un k entero tal que se cumpla n = j*k
Ahora bien, este k no puede ser cualquier número, debe ser menor a j. Por qué? Porque si k fuese igual a j estariamos en el caso de C = 0, lo que haría j a la raiz cuadrada de n y ese caso ya está contemplado. Si k fuese mayor a j, y j es mayor a la raiz cuadrada de n, entonces claramente como j*j > n se cumple que k*j > n. De modo que a k no le queda otra que ser menor a j. Pero como k es menor a j, y k es divisor de n por definición, de existir k ya lo habría encontrado en una iteración previa. De modo que k no existe si j es mayor a la raiz cuadrada de n.

Espero que se entienda, cualquier cosa me preguntás.

Saludos!

Me alegra que al final hayas entendido, cualquier duda que te haya quedado por el medio podés preguntar, prometo que no muerdo.

Es más fácil si piensas en los posibles factores de los números:

16:
1 x 16
2 x 8
4 x 4
8 x 2
16 x 1

9:
1 x 9
3 x 3
9 x 1

15:
1 x 15
3 x 5
5 x 3
15 x 1

30:
1 x 30
2 x 15
5 x 6
6 x 5
15 x 2
30 x 1

Como puedes ver los factores se repiten después de la raíz cuadrada del número y como al dividir el número entre otro número j también incluye el resultado como factor posible de n, terminas descartando dos números en lugar de uno.