입력이 최대 1000000000이 될 수 있다는 점을 감안할 때 더 많은 시간과 메모리 효율적인 프로그램을 어떻게 작성할 수 있습니까? (m과 n 사이의 모든 소수 인쇄)

다음은 아래 코드입니다 (CP qs에 해당)

실행 시간 제한은 6 초이지만 내 코드가 더 느립니다.

더 많은 메모리와 시간을 효율적으로 만들 수있는 방법은 무엇입니까?

• 입력 : 입력은 한 줄의 테스트 케이스 수 t 로 시작 합니다 ( t <= 10 ).

• 다음 t 줄 각각 에는 공백으로 구분 된 두 개의 숫자 m 과 n ( 1 <= m <= n <= 1000000000 , nm <= 100000 )이 있습니다.

• 출력 : 모든 테스트 케이스에 대해 m <= p <= n , 한 줄에 하나의 숫자, 빈 줄로 구분 된 테스트 케이스가 되도록 모든 소수 p를 인쇄합니다 .

#include <stdio.h>
#include <stdlib.h>

int main(void) {
    long int t,m,n,i,j,k;
    //printf("Enter number of testcases:\n");
    scanf("%ld",&t);
    long int test[t][2];
    for(i=0;i<t;i++){
        //printf("Enter m,n:\n");
        scanf("%ld %ld",&test[i][0],&test[i][1]);
    }
    
    for(k=0;k<t;k++){    
        for(i=test[k][0];i<=test[k][1];i++){
            for(j=2;j*j<i*i;j++){
                if(i%j==0)
                    break;
            }
            if(j==i){
                printf("%ld\n",i);
                }
            }
            printf("\n");
    }
    return 0;
}