Каков наилучший способ реализации алгоритмов поиска простых чисел в Java? Как мы создаем библиотечные классы и используем их тогда в Java?

Question

Я хочу создать библиотечные классы на Java и использовать их в своих будущих программах. Я хочу, чтобы эти библиотечные классы находили простые числа до определенного числа или даже следующего простого числа, или вы можете сказать, решить большинство основных вещей, связанных с простыми числами.

1. Я никогда не создавал Java Library Class. Я стремлюсь узнать, что делает это. Пожалуйста, помогите мне без этого, указав учебник или что-то. Я знаком с NetBeans IDE.
2. Я обнаружил несколько алгоритмов, таких как Сито Эратосфена и Сито Аткина . Было бы здорово, если бы вы могли указать еще несколько таких эффективных алгоритмов. Я не хочу, чтобы они были лучшими, но, по крайней мере, достаточно хорошими. Моя цель состоит в том, чтобы научиться нескольким вещам путем их реализации. Поскольку у меня мало практического опыта программирования, я хочу сделать это, чтобы улучшить свои навыки.
3. Мой друг предложил мне использовать потоковые классы, и он что-то говорил о его реализации, передавая вывод одного файла в качестве входного для другого, чтобы сделать мой код чистым. Я не очень хорошо его понял. Прошу прощения, если я сказал что-то не так. В этой связи я хочу спросить, является ли это эффективным и оригинальным способом делать то, что я хочу делать. Если да, скажите, пожалуйста, как это сделать, а если нет, укажите другой способ сделать это.

У меня есть базовые знания языка Java. На этом предприятии я хочу достичь опыта кодирования, потому что это то, что все здесь предложили, «взять на себя такие мелочи и учиться самостоятельно»

спасибо всем заранее

привет

shahensha

EDIT: В Сите Эратосфена и других нам необходимо хранить числа от 2 до n в структуре данных. Где я должен хранить это? Я знаю, что могу использовать динамическую коллекцию, но это небольшой вопрос ... Если я хочу найти простые числа порядка миллиардов или даже больше (я буду использовать Big Integer, без сомнения), но все это будет храниться в куче право? Есть ли страх переполнения? Даже если это не будет хорошей практикой? Или лучше хранить числа или список (над которыми мы будем выполнять действия в зависимости от используемого нами алгоритма) в файле и получать к нему доступ? Извините, если мой вопрос был слишком нубистским ...

Answer 1

«Сито Эратосфена» - хороший алгоритм для поиска простых чисел. Если вы будете использовать Google, вы можете найти готовую реализацию в java .

Answer 2

Я добавлю несколько мыслей к этому:

1. Технически нет ничего особенного в классе библиотеки, просто в том, как вы его используете.На мой взгляд, самое главное, что вы серьезно думаете о своем публичном API.Сделайте его достаточно полезным, чтобы быть полезным для ваших потенциальных абонентов, оставьте его достаточно маленьким, чтобы иметь возможность свободно изменять внутреннюю реализацию по своему усмотрению, и убедитесь, что у вас есть хорошее понимание того, что ваша библиотека делает делаети что он не делает.Не пытайся делать все, просто делай одну вещь хорошо.(И API обычно распространяется и на документацию, убедитесь, что вы пишете приличный Javadocs .)
2. Начните с любого из них, так как они в порядке.Если вы хорошо спроектируете свой API, вы можете изменить это в любое время и развернуть версию 1.1, которая использует другой алгоритм (или даже использует JNI для вызова нативной библиотеки C), и ваши абоненты могут просто вставить новый JAR и использовать вашкод даже без перекомпиляции.Не забывайте, что преждевременная оптимизация - корень всего зла;не беспокойтесь о том, чтобы сделать вашу первую версию быстрой , но сосредоточьтесь на том, чтобы сделать ее правильной и чистой.
3. Я не уверен, почему ваш друг предлагал потоки.Потоки - это способ работы с вводом и выводом необработанных байтов, который полезен при чтении из файлов или сетевых подключений, но, как правило, не является хорошим способом вызова другого метода Java.Ваша библиотека не должна беспокоиться о вводе и выводе, она просто должна предложить несколько методов для численных расчетов.Поэтому вы должны реализовать методы, которые принимают целые числа (или все, что подходит) и возвращают целые числа.

Например, вы можете реализовать:

/**
 * Calculates the next prime number after a given point.
 *
 * Implementation detail: callers may assume that prime numbers are
 * calculated deterministically, such that the efficiency of calling
 * this method with a large parameter is not dramatically worse than
 * calling it with a small parameter.
 *
 * @param x The lower bound (exclusive) of the prime number to return.
 * Must be strictly positive.
 * @return Colloquially, the "next" prime number after the given parameter.
 * More formally, this number will be prime and there are no prime numbers
 * less than this value and greater than <code>x</code> that are also
 * prime.
 * @throws IllegalArgumentException if <code>x</code> is not strictly
 * positive.
 */
public long smallestPrimeGreaterThan(long x);

/**
 * Returns all prime numbers within a given range, in order.
 *
 * @param lowerBound The lower bound (exclusive) of the range.
 * @param upperBound The upper bound (exclusive) of the range.
 * @return A List of the prime numbers that are strictly between the
 * given parameters.  This list is in ascending order.  The returned
 * value is never null; if no prime numbers exist within the given
 * range, then an empty list is returned.
 */
public List<Long> primeNumbersBetween(long lowerBound, long upperBound);

Нет потоков в поле зрения!Использование потоков, таких как вывод на консоль, должно обрабатываться приложениями, которые используют вашу библиотеку, а не самой библиотекой.Это то, что я имел в виду в своем первом замечании о том, чтобы понять, что ваша библиотека делает и чего не делает.Вы просто генерируете простые числа;звонящий должен сделать с ними что-нибудь классное.

Answer 3

`IMO, не думайте, что вы создаете библиотеку (файл .jar в соответствии с моей интерпретацией этого вопроса).

Сначала сосредоточьтесь на создании простого класса Java, например:

//SieveOfEratosthenes.java
  public class PrimeSieve{
    public static void main(String args[])
    {
    int N = Integer.parseInt(args[0]);
             // initially assume all integers are prime
    boolean[] isPrime = new boolean[N + 1];
    for (int i = 2; i <= N; i++) {
        isPrime[i] = true;
    }

    // mark non-primes <= N using Sieve of Eratosthenes
    for (int i = 2; i*i <= N; i++) {

        // if i is prime, then mark multiples of i as nonprime
        // suffices to consider mutiples i, i+1, ..., N/i
        if (isPrime[i]) {
            for (int j = i; i*j <= N; j++) {
                isPrime[i*j] = false;
            }
        }
    }

    // count primes
    int primes = 0;
    for (int i = 2; i <= N; i++) {
        if (isPrime[i]) primes++;
    }
    System.out.println("The number of primes <= " + N + " is " + primes);
}
}

Теперь следующий шаг;Реализуя его для больших значений, вы всегда можете использовать BigInteger.ТАК вопросы, относящиеся к тому же:

1. Простые числа Java BigInteger
2. Проблемы с java.math.BigInteger
3. Реализация BigNums

Попробуйте прочитать все вопросы, связанные с классом BigInteger на SO, BigInteger Помеченные вопросы.

Надеюсь, это поможет.

Answer 4

1. Не существует такой вещи, как "библиотечный класс". Я полагаю, вы хотите создать класс таким образом, чтобы он выполнял свою работу повторно. Способ сделать это - иметь чистый интерфейс - с минимальными (если есть) привязками к другим библиотекам или к вашей среде выполнения (вашему основному классу и т. Д.).

2. Два упомянутых вами слова "достаточно хороши". Для вашей цели вам не нужно смотреть дальше.

3. Просто прочитайте из System.in и напишите в System.out и все. Хотя в вашем случае читать нечего.

Чтобы достичь того, что, на мой взгляд, является вашей целью, вам нужно написать основной класс, который управляет средой исполнения - функцию main, инициализировать ваш алгоритм, итеративно искать следующий простой код и записать его в System.out. Конечно, вам понадобится другой класс для реализации алгоритма. Он должен содержать внутреннее состояние и предоставлять метод для поиска следующего простого числа.

Answer 5

Но если сравнивать, сито Аткина быстрее, чем сито Эратосфена:

http://en.wikipedia.org/wiki/Prime_number_counting_function Также обратитесь к этой ссылке, где различные функции объяснены ясно :)

Удачи ..