글 읽기 - 10^12의 배열크기 할당하는법

lys312510 4년 전 0

은 없죠..?

에라토스테네스 체를 구현하려고하는데

입력범위가 10^12라서 bool로 할당을 하려는데 안되네여..

방법 자체가 잘못됬나요

#include<cstdio>
#include<string.h>
#include<stack>
#include<string>
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;

//1000000000002
bool arr[1000000000001];
queue<long long>brr;

int main()
{
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);

    long long a;
    cin >> a;

    if(a == 1)
    {
        cout << 1;
        return 0;
    }

    arr[0] = true;
    arr[1] = true;
    for(long long i = 2; i<=a ;i++)
    {
        if(arr[i] == true )
        {
            continue;
        }
        for(long long k = i*i ; k <= a; k *= i)
        {
            arr[k] = true;
        }
    }
    for(long long i = 2; i<=a ;i++)
    {
        if(arr[i] == false)
        {
            brr.push(i);
        }
    }


    long long b = a;
    //long long i = 2 ;
    long long j = 1;
    long long sum = 1;

        long long i = brr.front();
        brr.pop();
        while(i <= b)
        {
            if(b%i == 0 )
            {
                b /= i;
                j *= i;
            }
            else//(b%i != 0 )
            {
                if(j != 1)
                {
                    sum *= (j/i)*(i-1);
                    j = 1;
                }
                 i = brr.front();
                brr.pop();
            }
        }

    if(j != 1)
    {
        sum *= ((j/i)*(i-1));
    }
    cout << sum ;
    return 0;
}

djm03178 4년 전 0

네, 그렇게 풀면 안 되는 문제입니다.

설령 할당이 가능하다고 하더라도, 에라토스테네스의 체를 10^12개에 대해 시간 안에 돌릴 수는 없습니다.

lys312510 4년 전 0

에라토스테네, 큐 안쓰고 그냥 소인수분해하는 식으로했는데

시간 초과가 나서요

더 시간을 줄일 방법이 없나요?

//구하는과정
    while(i <= b)
    {
        if(b%i == 0 )
        {
            b /= i;
            j *= i;
        }
        else//(b%i != 0 )
        {
            if(j != 1)
                sum *= (j/i)*(i-1);
            j = 1;
            i++;
        }
    }
    if(j != 1)
       sum *= (j/i)*(i-1);

lys312510 4년 전 0

살짝 정정하자면 없는건 아니겠죠 있으니까 시간초과가 나겠지만..

sait2000 4년 전 0

오일러 토션트 계산하는 문제 아닌가요? 소인수 분해하면 풀 수 있는데 제곱근까지만 루프를 돌면 됩니다.

djm03178 4년 전 0

오일러 토션트라는 걸 처음 알게 됐네요. 찾아보니 포함 배제로 증명이 되는데 그보다 훨씬 간단한 식으로 풀 수 있군요.

lys312510 4년 전 0

제가 풀려고했던 방식이 오일러 토션튼데..

큰 소수일경우에 반복횟수가 O(N)이라 이 처리가 안되네용 ㅠ

djm03178 4년 전 0

sait님이 말씀하셨던 것처럼 루프는 제곱근까지만 돌면 됩니다. sqrt(N)보다 큰 수로는 나누어볼 필요가 없기 때문입니다.

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

문제

문제

출처

ICPC

10^12의 배열크기 할당하는법

lys312510 4년 전 0

djm03178 4년 전 0

lys312510 4년 전 0

lys312510 4년 전 0

sait2000 4년 전 0

djm03178 4년 전 0

lys312510 4년 전 0

djm03178 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말