글 읽기 - 2023번 메모리 초과를 어떻게 하면 극복할 수 있을까요?

lety 8년 전 0

메모리 제한이 4MB라니.. 에라토스테네스의 체 쓰지 않고 해결 할 수 있는 방법이 있을까요?

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

#define bool int
#define true 1
#define false 0 

bool prime[100000000]; // 소수 = 1 , 그외 = 0

eratos(int n);

int main()
{
	int n;
	int i;
	int m;
	int temp;
	bool issingle;
	scanf("%d",&n);
	
	eratos(pow(10,n));
	
	m = pow(10,n);
	
	for(i= pow(10,n-1);i<m;i++)
	{
		temp = i;
		issingle = true;
		// n 자리의 수가 1자리 까지 다 소수
		while(temp>0)
		{
			if(prime[temp] == 0)
			{
				issingle = false;
				break;
			}
			temp /= 10;
		}
		if(issingle)
		{
			printf("%d\n",i);
		}
	}
	
return 0;
}

eratos(int n)
{
	int i,j;
	int p = (int)sqrt(n);	
	memset(prime,1,sizeof(prime));
	
	prime[0] = prime[1] = false;
	
	for(i=2;i<=p;i++)
	{
		if(prime[i])
		{
			for(j=i*i;j<=n;j+=i)
			{
				prime[j] = 0;
			}
		}
	}
}

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

문제

문제

출처

ICPC

2023번 메모리 초과를 어떻게 하면 극복할 수 있을까요?

lety 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말