結果

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

ソースコード

diff #
raw source code 

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

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

    IS_PRIME = ERATOSTHENES(N)
    ! PRINT *, IS_PRIME(:)
    ALLOCATE(PRIME(N))
    J = 1
    DO I = 1, N
        IF (IS_PRIME(I)) THEN
            PRIME(J) = I
            J = J + 1
        END IF
    END DO
    PRIME_COUNT = J - 1

    ! この後において、勝敗判定を行う。
    ALLOCATE(WIN_LOSE(N))
    ! WIN_LOSE = TRUE(勝ち) FALSE(負け)
    WIN_LOSE = .FALSE.
    DO I = 4, N
        DO J = 1, PRIME_COUNT
            P = PRIME(J)

            IF (P >= I - 1) EXIT
            
            IF (.NOT. WIN_LOSE(I - P)) THEN
                WIN_LOSE(I) = .TRUE.
                EXIT
            END IF
        END DO
    END DO

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

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

        ALLOCATE(IS_PRIME(N))
        IS_PRIME = .TRUE.

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

        IS_PRIME(1) = .FALSE.
        IS_PRIME(2) = .TRUE.
        DO I = 2, N
            IF (.NOT. IS_PRIME(I)) THEN
                CYCLE
            END IF

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

            DO J = I * I, N, I
                IS_PRIME(J) = .FALSE.
            END DO
        END DO

        RETURN
    END FUNCTION ERATOSTHENES
END PROGRAM MAIN
0