글 읽기 - 시간초과가 자꾸 뜹니다.

tjehdgns0925 4년 전 0

is_square함수

먼저 가장 큰수보다 작은 값들을

차례대로 저장하고

square_number함수안에서 i=는 범위 안의 숫자 하나 하나를 읽어서

isnt_prime 즉 소수가 아닌 수를 판별해 그것들중 arrMax[0~cnt]까지 나누어떨어지는경우 숫자를 더해서

최종적으로 Max~Min 사이의 숫자에서 sum을 빼주는것인데

시간초과가 뜹니다. 어떤식으로 보완해야하는지 조언좀 부탁드립니다.

#include <iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;

long long Min, Max;
long long arrMax[1000001];
long long cnt;

void is_square(int m) {          //범위 내의 제곱수 저장

	for (long long i =2; i*i <=Max; i++) {

			arrMax[cnt] = i*i;
		//printf("arrMax[%lld]=%lld\n",cnt,arrMax[cnt]);
			cnt++;
		}
			
	

}

int isnt_prime(int n) {
	//printf("%d일때 소수인가 ?\n", n);
	for (int i = 2; i<=int(n / 2); i++) {
	//	printf("%d\n", i);
		if (n %i == 0) { //나누어 떨어지면 소수가 아니다
			return 1;
		}
		
	}
	return 0;
}



long long square_number() {
	long long count1;
	long long sum = 0;
	
	
		for (long long i = Min; i <= Max; i++) {
		//	printf("i=%d일때\n", i);
			if (1 == isnt_prime(i)) {  //소수가 아니어야
			//	printf("i는 소수가 아니다 \n");
				for (long long j = 0; j < cnt; j++) {
				//	printf("i=%lld  >=arrMax[j]=%lld?\n", i, arrMax[j]);
					if (i < arrMax[j]) {
					//	printf("비교할 필요 없음 \n");
						break;
					}
					else {
						if (i%arrMax[j] == 0) {
							sum = sum + 1;
							break;
						}
					}
				}
			}
			else {
				//printf("i=소수일때 그냥 더해줌\n",i);
			}
			
		}
	
		
		
	
	return sum;
}


int main(void) {	

	cin >> Min >> Max;
	cnt = 0;
	memset(arrMax, 0, sizeof(arrMax));
	is_square(Max);    //제곱수 저장
	
	//printf("사이에 제곱수는 =%d 개있음\n", cnt);
	cout << (Max-Min+1)-square_number() << endl;
	
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과가 자꾸 뜹니다.

tjehdgns0925 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말