일단 10000만 입력해봐도 연산 시간이 매우 길어진다는 걸 눈치채실 수 있을 겁니다.

pn(p) 함수는 시간복잡도가 O(p)입니다. 3행의 루프문 때문입니다.

이후 각 테스트케이스를 처리하는 과정에서, 17행의 루프의 시간복잡도를 분석해봅시다.
k가 1부터 n까지 루프를 도는데 pn(k)를 한 번 호출할 때마다 O(k)번의 루프를 돌기 때문에 이 루프만 보면 시간복잡도가 O(n^2)입니다.
(덤으로 k가 소수일 때 pn(z)가 연산되는 시간복잡도도 포함할 수 있긴 한데, 내용도 어렵고, 이를 고려해도 여전히 O(n^2)이기 때문에 생략하겠습니다.)

n의 최댓값은 10000입니다. 10000^2은 10^8입니다. 이 문제는 여러 개의 테스트 케이스로 이루어져 있기도 한 만큼, 10^8회의 루프는 여러 번 시행하기엔 무리가 큽니다.
따라서 시간 초과가 나게 됩니다.

--------

우선 작성하신 코드에서, 특정 수 p가 소수인지 아닌지 판별하는 것은 O(루트(p)) 안에 해결할 수 있습니다. 3행의 루프문에서 p를 나눌 수 있는 수가 있는지 없는지 판별하는 과정에서, 사실은 루트p 이하인 정수까지만 나눠봐도 충분합니다.

예를 들어 17이 소수인지 아닌지 판별하는 과정을 생각해봅시다. 루트17 이하의 가장 큰 정수는 4입니다. 일단 2부터 4까지로 17을 나눠보면 안 나눠짐을 알 수 있습니다.
여기서, 4까지의 정수는 17을 나눌 수 없지만, 17을 나눌 수 있는 5 이상의 어떤 정수 d가 존재한다고 해봅시다. 이는 곧 어떤 정수 x에 대해서 d*x = 17이라는 뜻이므로, x 역시 17을 나눌 수 있어야 합니다.
여기서 d는 5 이상이므로 x는 커봐야 4입니다. 하지만 앞서 4 이하의 정수는 17을 나눌 수 없다고 했습니다. 따라서 17을 4까지의 정수로만 나눠봐도 17이 소수임을 알 수 있습니다.
이를 일반화시키면 p가 소수임을 판별하기 위해선 루트(p)까지만 판별하면 됨을 알 수 있습니다.

그렇게 하면 pn(p)의 시간복잡도를 O(루트p)까지 내릴 수 있습니다. 이외에도 한 가지만 더 생각하면 17행의 루프를 조기에 탈출할 수도 있는데 한번 직접 생각해보세요.

--------

한편 주어진 수가 소수인지 아닌지 판별하는 횟수가 적을 땐 보통 O(루트(p))인 소수 판별 함수로도 충분하지만, 엄청나게 많은 수에 대해 소수판정을 해야 할 경우, 그 수의 범위 안에 있는 모든 수에 대해서 각각이 소수인지 아닌지 "미리" 판별해놓고, 각 수의 소수 판별을 O(1)에 해낼 수도 있습니다.

n 이하의 소수를 모두 찾아내는 것은 "에라토스테네스의 체"를 사용해 할 수 있습니다. 검색해보시면 많은 자료가 있으니 모르신다면 직접 공부해보세요.

소수 판별 외에도 주어진 수에 대해 특정 값을 계산해야 하는 횟수가 엄청 많을 때, 프로그램 실행 직후 미리 모든 값에 대해 전부 계산해놓고 필요할 때 빠르게 끌어다 쓰는 테크닉을 활용할 수 있습니다. 이를 보통 "전처리"라고 부릅니다. 언제 전처리를 하는 것이 유리한지는 문제를 많이 접하다보면 알게 됩니다.

친절하게 알려주셔서 감사합니다.

깊게 공부해야 될 것이 많다는 걸 깨닫습니다.

번외로 한가지 더 궁금한게 있는데

시간복잡도에 관한것은 코딩에 있어서 많이 중요한 부분인가요?

코딩에 있어서 부가적인 부분인건지 필수적인 부분인건지 궁금합니다.