Java：查找小于 n 的素数列表（其中 n 是一个 BigNum）

Question

此代码仅打印出 2 个，我不明白为什么它不起作用。我认为这与我的链表实现有关。一开始我只想找到小于 100 的素数。

素数（或素数）是大于 1 的自然数，除了 1 和它本身之外没有正约数。大于1且不是质数的自然数称为合数。

import java.math.*;
import static java.math.BigInteger.*;
class Node {
    BigInteger data;
    Node small;
    Node large;
    public Node(BigInteger data) {
        this.data = data;
        small = null;
        large = null;
    }
}
class TreeList {
    public static void join(Node a, Node b) {
        a.large = b;
        b.small = a;
    }
    public static Node append(Node a, Node b) {
        if (a == null) return(b);
        if (b == null) return(a);
        Node aLast = a.small;
        Node bLast = b.small;
        join(aLast, b);
        join(bLast, a);   
        return(a);
    }
    public static Node treeToList(Node root) {
        if (root == null) return (null);
        Node aList = treeToList(root.small);
        Node bList = treeToList(root.large);
        root.small = root;
        root.large = root;
        aList = append(aList, root);
        aList = append(aList, bList);   
        return(aList);
    }
    public static void treeInsert(Node root, BigInteger newData) {
        if (newData.compareTo(root.data) == 0) {
            if (root.small != null) treeInsert(root.small, newData);
            else root.small = new Node(newData);
        }
        else {
            if (root.large != null) treeInsert(root.large, newData);
            else root.large = new Node(newData);
        }
    }
    public static void printTree(Node root) {
        if (root == null) return;
        printTree(root.small);
        System.out.print(root.data.toString());
        printTree(root.large);
    }
    public static void printList(Node head) {
        Node current = head;
        while (current != null) {
            System.out.print(current.data.toString() + " ");
            current = current.large;
            if (current == head) break;
        }
        System.out.println();
    }
    public static void main(String[] args) {
        BigInteger count = BigInteger.valueOf(1);
        BigInteger myPrime = BigInteger.valueOf(2);
        BigInteger two = BigInteger.valueOf(2);
        BigInteger three = BigInteger.valueOf(3);
        Node root = new Node(myPrime);
        Node head = treeToList(root);

        boolean isPrime;

        BigInteger n = new BigInteger("100");

        for (BigInteger i = three; count.compareTo(n) == 0; i = i.add(two)) {
            isPrime = true;
            for (BigInteger j = three; (j.multiply(j)).compareTo(i) == 0 && isPrime; j = j.add(two))
                if (i.mod(j) == BigInteger.ZERO) isPrime = false;
            if (isPrime) {
                count = count.add(BigInteger.ONE);   
                myPrime = i;
                if (myPrime.compareTo(n) == 0) treeInsert(root, myPrime);
            }
        }
        printList(head);
    }
}

Answer 1

你的循环根本不是运行，因为它 return false 在 count.compareTo(n) == 0.

For 循环，仅在第二条语句 return 为真时运行。

您的第二个 for 循环也有问题。

Java：查找小于 n 的素数列表（其中 n 是一个 BigNum）

Java: Find list of primes less than n (where n is a BigNum)

java

primes