script.js

// エラトステネスの篩で 10^6 までの素数リストを作成
const sieveLimit = 1000000;  // 100万までの素数リストを作成
const smallPrimes = [];
const isPrimeArray = Array(sieveLimit + 1).fill(true);

function initializeSieve() {
    isPrimeArray[0] = isPrimeArray[1] = false;
    for (let i = 2; i <= sieveLimit; i++) {
        if (isPrimeArray[i]) {
            smallPrimes.push(i);
            for (let j = i * i; j <= sieveLimit; j += i) {
                isPrimeArray[j] = false;
            }
        }
    }
}

// 試し割り法による素数判定
function isPrime(n) {
    if (n <= sieveLimit) {
        return isPrimeArray[n];
    }

    // nがsieveLimitより大きい場合、smallPrimesで試し割り
    for (let p of smallPrimes) {
        if (p * p > n) break;  // √N までの素数で割り切れなければ素数
        if (n % p === 0) return false;
    }
    return true;
}

// DFSを用いた順列生成
function dfs(nums, path, k, result) {
    if (path.length === k) {
        // 数字を整数に変換
        let num = parseInt(path.join(''), 10);
        let remainingNums = nums.filter(n => !path.includes(n));
        result.push({ num, remainingNums });
        return;
    }

    for (let i = 0; i < nums.length; ++i) {
        let nextNums = nums.slice(0, i).concat(nums.slice(i + 1));
        dfs(nextNums, [...path, nums[i]], k, result);
    }
}

// 残りの数字で作れる素数を判定
function canMakePrime(remainingNums) {
    let remainingPermutations = findPermutations(remainingNums, remainingNums.length);
    return remainingPermutations.some(isPrime);
}

// 順列を取得する関数
function findPermutations(nums, k) {
    let result = [];
    dfs(nums, [], k, result);
    return result.map(entry => entry.num);
}

// 順列を生成し、素数のみ表示
function generatePermutations() {
    let numsInput = document.getElementById("numbers").value;
    let nums = numsInput.split(",").map(num => parseInt(num.trim())).filter(num => !isNaN(num));
    let choose = parseInt(document.getElementById("choose").value);
    let checkRemainder = document.getElementById("checkRemainder").checked; // チェックボックスの状態を取得

    if (isNaN(choose) || choose <= 0 || choose > nums.length) {
        alert("有効な選択数を入力してください。");
        return;
    }

    let permutations = [];
    dfs(nums, [], choose, permutations);

    let resultsDiv = document.getElementById("results");
    resultsDiv.innerHTML = "";
    let fragment = document.createDocumentFragment();

    permutations.forEach(({ num, remainingNums }) => {
        if (isPrime(num)) {
            let resultElement = document.createElement("div");
            resultElement.classList.add("result-item");

            // 余りの数の素数判定をするかどうかチェックボックスで決定
            if (checkRemainder && canMakePrime(remainingNums)) {
                resultElement.classList.add("result-item-remain");
            }

            resultElement.textContent = num;
            fragment.appendChild(resultElement);
        }
    });

    resultsDiv.appendChild(fragment);
}

// 初期化
initializeSieve();