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

Question

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

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

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

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

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

С уважением

shahensha

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

6

java algorithm streaming biginteger class-library

Источник

user341255 11 ноя '10 в 08:32

5 ответов

Другие вопросы по тегам java algorithm streaming biginteger class-library

user205270 11 ноя '10 в 08:37 2010-11-11 08:37 · Answer 1 · 2010-11-11 08:37

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

3

Источник

user205270 11 ноя '10 в 08:37

user45664 12 ноя '10 в 09:53 2010-11-12 09:53 · Answer 2 · 2010-11-12 09:53

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

Нет ничего технически отличного в библиотечном классе, просто как вы его используете. На мой взгляд, самое главное, что вы серьезно думаете о своем публичном API. Сделайте это достаточно полезным, чтобы быть полезным для ваших потенциальных абонентов, оставьте его достаточно маленьким, чтобы иметь свободу изменять внутреннюю реализацию по своему усмотрению, и убедитесь, что у вас есть хорошее понимание того, что делает ваша библиотека, а что нет. делать. Не пытайся делать все, просто делай одну вещь хорошо. (И API обычно распространяется и на документацию, убедитесь, что вы пишете приличные Javadocs.)
Начните с любого из них, так как они в порядке. Если вы хорошо спроектируете свой API, вы можете изменить это в любое время и развернуть версию 1.1, которая использует другой алгоритм (или даже использует JNI для вызова нативной библиотеки C), и ваши абоненты могут просто вставить новый JAR и использовать свой код даже без перекомпиляции. Не забывайте, что преждевременная оптимизация - корень всего зла; не беспокойтесь о том, чтобы сделать вашу первую версию быстрой, но сосредоточитесь на том, чтобы сделать ее правильной и чистой.
Я не уверен, почему твой друг предлагал потоки. Потоки - это способ обработки ввода и вывода необработанных байтов - полезен при чтении из файлов или сетевых подключений, но, как правило, не является хорошим способом вызова другого метода 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);

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

user498447 11 ноя '10 в 08:53 2010-11-11 08:53 · Answer 3 · 2010-11-11 08:53

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

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

user459638 12 ноя '10 в 07:29 2010-11-12 07:29 · Answer 4 · 2010-11-12 07:29

`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. ТАК вопросы, относящиеся к тому же:

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

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

user402011 11 ноя '10 в 08:43 2010-11-11 08:43 · Answer 5 · 2010-11-11 08:43

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

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

Удачи..

1

Источник

user402011 11 ноя '10 в 08:43