Honestamente falando, é exatamente pelo fato de estar no primeiro semestre em Ciência da Computação é que tu tá sofrendo pra resolver problemas como esse. Geralmente a faculdade não te ensina certas coisas específicas de programação competitiva e infelizmente, algumas coisas tu terá de aprender por fora...
O método de solução que tu deverá usar se trata do Crivo de Eratóstenes (Sieve of Eratosthenes) que visa encontrar um limite para um número de divisores que um número composto pode ter.
Em termos de complexidade de execução do algoritmo, isso tu irá aprender na sua faculdade, mas já procure saber de sua importância: Procure sobre Notação Big-O
Na notação Big-O, a complexidade normal de busca de números primos é algo Linear ou O(n) por utilizar apenas 1 FOR para percorrer todos os valores possíveis de 1 até N. Contudo, o Crivo baixa isso pra O[sqrt(n)] percorrendo até a Raiz Quadrada de N.
Analisando a entrada, esta diz que é até 2^31-1. Em potência de 10, isso dá mais de 1 x 10^9 ou um número de 10 dígitos. Então, a partir daí, assume-se que:
a) Uma variável INT comum já assume todos os valores até 2^31-1.
b) Essa é a mais importante: de 1 até 10^9, o compilador NÃO consegue responder em 1 segundo. Em C, de 1 até 10^6 é garantido o tempo de 1 segundo, se for até 10^7, o tempo começará a se aproximar de 1 segundo e isso pode dar problemas em outras linguagens.
É por essas e outras que, muitas das vezes, o limite superior assumido pra resposta de 1 segundo é até 10^6 ou levemente inferior a 10^7.
c) Então se temos 2^31-1 ou mais de 10^9 como limite, colocar o limite do FOR como N/2 não resolve, pois o valor será superior a 5 x 10^8 e ainda seria alto.
Com o Crivo, o valor de N será superior a 10^4,5 (10^9/2), mas já será possível dar o resultado em 1 segundo.