[단계09] 기본 수학2 (11문제)

www.acmicpc.net/step/10

 

● [문제번호 1978] 소수찾기

#include <stdio.h>

int main()
{
    int N;
    scanf("%d", &N);
    
    int count = 0;
    
    for(int i = 0; i < N; i++)
    {
        int temp;
        scanf("%d", &temp);
        
        // 2이상의 경우
        if(temp > 2)
        {
            // 0이면 소수, 1이면 소수 아님
            int flag = 0;
            
            for(int i = 2; i < temp; i++)
            {
                // 나누어지는 수가 있는 경우 != 소수
                if(temp % i == 0)
                {
                    flag = 1;
                    break;
                }
            }
            
            // 소수인 경우
            if(flag == 0)
                count++;
        }
        
        // 2인 경우
        else if(temp == 2)
            count++;
    }
    
    printf("%d", count);
    
    return 0;
}

 

● [문제번호 2581] 소수

#include <stdio.h>

int decimal(int n)
{
    if(n == 2)
        return n;
    else if(n == 1)
        return 0;
    
    for(int i = 2; i < n; i++)
    {
        if(n % i == 0)
            return 0;
    }
    
    return n;
}

int main()
{
    int M, N;
    scanf("%d", &M);
    scanf("%d", &N);
    
    int total = 0;
    int min = 0;
    
    int flag = 0;
    for(int i = M; i <= N; i++)
    {
        total += decimal(i);
        if(flag == 0 && total > 0)
        {
            min = total;
            flag = 1;
        }    
    }
    
    if(total == 0)
        printf("-1");
    else
        printf("%d\n%d", total, min);
    
    return 0;
}

 

● [문제번호 11653] 소인수분해

#include <stdio.h>

int main()
{
    int N;
    scanf("%d", &N);
    
    if(N == 1)
        return 0;
    
    int temp = 2;
    while(1)
    {
        if(N % temp == 0)
        {
            printf("%d\n", temp);
            N /= temp;
        }
        else
            temp++;
        
        if(N == 1)
            break;
    }
    
    return 0;
}

 

● [문제번호 1929] 소수 구하기

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

int main()
{
    int M, N;
    scanf("%d %d", &M, &N);
    
    int *num;
    num = (int*)malloc((N + 1) * sizeof(int));
    
    num[0] = -1;
    num[1] = -1;
    
    for(int i = 2; i <= N; i++)
    {
        if(num[i] == -1)
            continue;
        
        int temp = 1;
        num[i * temp] = 1;
        
        while(1)
        {
            temp++;
            
            if(i * temp > N)
                break;
            
            num[i * temp] = -1;
        }
    }
    
    for(int i = M; i <= N; i++)
        if(num[i] == 1)
            printf("%d\n", i);
    
    free(num);
    
    return 0;
}

// 한 숫자마다 소수인지 판단을 하면 시간초과
// 따라서 범위까지의 숫자까지 소수를 먼저 가려낸다

 

● [문제번호 4948] 베르트랑 공준

#include <stdio.h>

int main()
{
    while(1)
    {
        int n;
        scanf("%d", &n);
        
        if(n == 0)
            break;
        else if(n == 1)
        {
            printf("%d\n", 1);
            continue;
        }
        
        int num[123456 * 2 + 1];
        
        num[0] = -1;
        num[1] = -1;
        
        for(int i = 2; i <= 2 * n; i++)
        {
            if(num[i] == -1)
                continue;
            
            int temp = 1;
            num[i * temp] = 1;
            
            while(1)
            {
                temp++;
                
                if(i * temp > 2 * n)
                    break;
                
                num[i * temp] = -1;
            }
        }
        
        int count = 0;
        for(int i = n + 1; i <= 2 * n; i++)
            if(num[i] == 1)
                count++;
        
        printf("%d\n", count);
    }
    
    return 0;
}

 

● [문제번호 9020] 골드바흐의 추측

#include <stdio.h>

int main()
{
    int T;
    scanf("%d", &T);
    
    int num[10001];
    num[0] = -1;
    num[1] = -1;
    
    for(int i = 2; i <= 10000; i++)
    {
        if(num[i] == -1)
            continue;
        
        num[i] = 1;
        int temp = 2;
        while(1)
        {
            if(i * temp > 10000)
                break;
            
            num[i * temp] = -1;
            
            temp++;
        }
    }
    
    for(int i = 0; i < T; i++)
    {
        int n;
        scanf("%d", &n);
        
        int a, b;
        if(n % 2 == 0)
        {
            a = n / 2;
            b = n / 2;
        }
        else if(n % 2 == 1)
        {
            a = n / 2;
            b = n / 2 + 1;
        }
        
        while(1)
        {
            if(num[a] == 1 && num[b] == 1)
                break;
            
            a--;
            b++;
        }
        
        printf("%d %d\n", a, b);
    }

    return 0;
}

 

● [문제번호 1085] 직사각형에서 탈출

#include <stdio.h>

int main()
{
    int x, y, w, h;
    scanf("%d %d %d %d", &x, &y, &w, &h);
    
    int gapx = w - x;
    int gapy = h - y;
    
    if(gapx > x)
        gapx = x;
    if(gapy > y)
        gapy = y;
    
    if(gapx < gapy)
        printf("%d", gapx);
    else
        printf("%d", gapy);

    return 0;
}

 

● [문제번호 3009] 네 번째 점

#include <stdio.h>

int main()
{
    int x1, y1;
    int x2, y2;
    int x3, y3;
    scanf("%d %d", &x1, &y1);
    scanf("%d %d", &x2, &y2);
    scanf("%d %d", &x3, &y3);
    
    int x4, y4;
    
    if(x1 == x2)
        x4 = x3;
    else if(x1 == x3)
        x4 = x2;
    else if(x2 == x3)
        x4 = x1;
    
    if(y1 == y2)
        y4 = y3;
    else if(y1 == y3)
        y4 = y2;
    else if(y2 == y3)
        y4 = y1;
    
    printf("%d %d", x4, y4);
    
    return 0;
}

 

● [문제번호 4153] 직각삼각형

#include <stdio.h>

int main()
{
    while(1)
    {
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);
        
        if(x == 0 && y == 0 && z == 0)
            break;
        
        int xx = x * x;
        int yy = y * y;
        int zz = z * z;
        
        
        if(xx + yy == zz)
            printf("right\n");
        else if(xx + zz == yy)
            printf("right\n");
        else if(yy + zz == xx)
            printf("right\n");
        else
            printf("wrong\n");
    }
    
    return 0;
}

 

● [문제번호 3053] 택시 기하학

#include <stdio.h>
#define PIE 3.1415926535897

int main()
{
    int R;
    scanf("%d", &R);
    
    printf("%lf\n", R * R * PIE);
    
    printf("%lf\n", R * R * 2.0);
    
    return 0;
}

 

● [문제번호 1002] 터렛

#include <stdio.h>

int main()
{
    int T;
    scanf("%d", &T);
    
    for(int i = 0; i < T; i++)
    {
        int x1, y1, r1;
        int x2, y2, r2;
        scanf("%d %d %d %d %d %d", &x1, &y1, &r1, &x2, &y2, &r2);
        
        if(x1 == x2 && y1 == y2)
        {
            if(r1 == r2)
                printf("%d\n", -1);
            else
                printf("%d\n", 0);
            
            continue;
        }
        
        int x = (x2 - x1) * (x2 - x1);
        int y = (y2 - y1) * (y2 - y1);
        int r = (r1 + r2) * (r1 + r2);
        
        // 안 겹친 경우
        if(x + y > r)
            printf("%d\n", 0);
        // 겹치지 않고 접한 경우
        else if(x + y == r)
            printf("%d\n", 1);
        // 겹치기 시작
        else if(x + y < r)
        {
            // r2를 큰 원으로 바꾸기
            if(r1 > r2)
            {
                int temp = x1;
                x1 = x2;
                x2 = temp;
                temp = y1;
                y1 = y2;
                y2 = temp;
                
                r = (r1 - r2) * (r1 - r2);
            }
            else
                r = (r2 - r1) * (r2 - r1);
            
            // r1의 원 전체가 겹치지 않은 경우
            if(x + y > r)
                printf("%d\n", 2);
            // r1의 원 전체가 겹치지만 접한 경우
            else if(x + y == r)
                printf("%d\n", 1);
            // r1이 r2의 내부로 들어간 경우
            else if(x + y < r)
                printf("%d\n", 0);
        }
    }
    
    return 0;
}