結果

問題 No.7 プライムナンバーゲーム
コンテスト
ユーザー iLL
提出日時 2026-03-09 15:26:35
言語 Fortran
(gFortran 15.2.0)
コンパイル:
gfortran _filename_ -O2 -o ./a.out
実行:
./a.out
結果
AC  
実行時間 17 ms / 5,000 ms
コード長 1,489 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,005 ms
コンパイル使用メモリ 40,172 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2026-03-09 15:28:14
合計ジャッジ時間 2,469 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

PROGRAM MAIN
    IMPLICIT NONE
    INTEGER :: N, I, J
    INTEGER, ALLOCATABLE, DIMENSION(:) :: IS_PRIME, WIN_LOSE

    READ *, N
    IF (N < 4) THEN
        PRINT *, 'Lose'
        RETURN
    END IF

    IS_PRIME = ERATOSTHENES(N)
    ! PRINT *, IS_PRIME(:)

    ! この後において、勝敗判定を行う。
    ALLOCATE(WIN_LOSE(N))
    ! WIN_LOSE = 1(勝ち) 0(負け)
    WIN_LOSE = 0
    DO I = 4, N
        DO J = 1, I - 2
            IF (IS_PRIME(J) == 0) THEN
                CYCLE
            END IF
            IF (WIN_LOSE(I - J) == 0) THEN
                WIN_LOSE(I) = 1
                EXIT
            END IF
        END DO
    END DO

    IF (WIN_LOSE(N) == 1) THEN
        PRINT *, 'Win'
    ELSE
        PRINT *, 'Lose'
    END IF

CONTAINS
    FUNCTION ERATOSTHENES(N) RESULT(IS_PRIME)
        IMPLICIT NONE
        INTEGER, INTENT(IN) :: N
        INTEGER, ALLOCATABLE, DIMENSION(:):: IS_PRIME
        INTEGER :: I, J

        ALLOCATE(IS_PRIME(N))
        IS_PRIME = 1

        ! エラトステネスの篩を実装するよ。
        ! IS_PRIME = 1(素数) 0(合成数・1)

        IS_PRIME(1) = 0
        IS_PRIME(2) = 1
        DO I = 2, N
            IF (IS_PRIME(I) == 0) THEN
                CYCLE
            END IF

            IF (I * I > N) THEN
                EXIT
            END IF

            DO J = I * I, N, I
                IS_PRIME(J) = 0
            END DO
        END DO

        RETURN
    END FUNCTION ERATOSTHENES
END PROGRAM MAIN
0