글 읽기 - 시간초과 해결법을 모르겠어요

skatjdehddms 2년 전 0

입력받은 수까지의 소수를 구해서 배열로 정리하고 그 소수들로 나누어가면서 소인수 분해를 하려고 했는데 적은 수는 잘 되는데 10000넘어가니까 오래 걸리더라구요 근데 어떤식으로 고쳐야하는지 감이 안잡혀요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdlib>

using namespace std;

int main()
{
	
	int a;
	cin >> a;
	int t = a;
	int *arr;//소수
	arr = new int[a];
	int k = 0;
	int k2 = 0;
	int* arr2;//인수
	arr2 = new int[a];
	for (int i = 2; i <= a; i++)
	{
		if (i == 2)
		{
			
			arr[k] = 2;
			k++;
		}
		else
		{
			for (int j = 2; j < i; j++)
			{
				if (i == 1)
					break;

				else if (i % j == 0)
				{
					break;
				}
				else
					if (j == i - 1)
					{
						arr[k] = i;
						k++;
					}
			}
		}
	}
	int c = 0;
	while (c<k)
	{
		if (t % arr[c] == 0)
		{
			arr2[k2] = arr[c];
			t /= arr[c];
			k2++;
		}
		else
		{
			c++;
		}
		if (t == 1)
			break;
	}

	for (int i = 0; i < k2; i++)
		cout << arr2[i] << endl;
	return 0;
}

drash99 2년 전 2

n이 입력되었으면 루트n 보다 작은 소수만 확인해주면 돼요

루트 n보다 큰 소수 두개 이상으로 소인수분해가 된다면 n보다 커지니까요.

만약 루트n보다 작은 소수로 더이상 나눠떨어지지 않으면 그 수는 소수고요.

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

문제

문제

출처

ICPC

시간초과 해결법을 모르겠어요

skatjdehddms 2년 전 0

drash99 2년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말