Как найти ближайшее простое число к заданному - Сайт, где вы сможете решить свои вопросы

Is there any nice algorithm to find the nearest prime number to a given real number? I only need to search within the first 100 primes or so.

At present, I’ve a bunch of prime numbers stored in an array and I’m checking the difference one number at a time (O(n)?).

asked Oct 15, 2009 at 21:12

Rather than a sorted list of primes, given the relatively small range targetted, have an array indexed by all the odd numbers in the range (you know there are no even primes except the special case of 2) and containing the closest prime. Finding the solution becomes O(1) time-wise.

I think the 100th prime is circa 541. an array of 270 [small] ints is all that is needed.

This approach is particularly valid, given the relative high density of primes (in particular relative to odd numbers), in the range below 1,000. (As this affects the size of a binary tree)

answered Oct 15, 2009 at 21:21

mjvmjv

72.7k14 gold badges112 silver badges156 bronze badges

If you only need to search in the first 100 primes or so, just create a sorted table of those primes, and do a binary search. This will either get you to one prime number, or a spot between two, and you check which of those is closer.

Edit: Given the distribution of primes in that range, you could probably speed things up (a tiny bit) by using an interpolation search — instead of always starting at the middle of the table, use linear interpolation to guess at a more accurate starting point. The 100th prime number should be somewhere around 250 or so (at a guess — I haven’t checked), so if (for example) you wanted the one closest to 50, you’d start about 1/5th of the way into the array instead of halfway. You can pretty much treat the primes as starting at 1, so just divide the number you want by the largest in your range to get a guess at the starting point.

answered Oct 15, 2009 at 21:15

Jerry CoffinJerry Coffin

471k80 gold badges621 silver badges1107 bronze badges

Answers so far are rather complicated, given the task in hand. The first hundred primes are all less then 600. I would create an array of size 600 and place in each the value of the nearest prime to that number. Then, given a number to test, I would round it both up and down using the floor and ceil functions to get one or two candidate answers. A simple comparison with the distances to these numbers will give you a very fast answer.

answered Oct 15, 2009 at 21:25

TimTim

9,10132 silver badges51 bronze badges

The simplest approach would be to store the primes in a sorted list and modify your algorithm to do a binary search.

The standard binary search algorithm would return null for a miss, but it should be straight-forward to modify it for your purposes.

answered Oct 15, 2009 at 21:14

Jeremy SteinJeremy Stein

19k16 gold badges68 silver badges83 bronze badges

The fastest algorithm? Create a lookup table with p[100]=541 elements and return the result for floor(x), with special logic for x on [2,3]. That would be O(1).

answered Oct 15, 2009 at 21:22

mobmob

117k18 gold badges149 silver badges283 bronze badges

You should sort your number in array then you can use binary search. This algorithm is O(log n) performance in worst case.

answered Oct 15, 2009 at 21:15

Ivan NevostruevIvan Nevostruev

28k8 gold badges65 silver badges82 bronze badges

public static boolean p(int n){

    for(int i=3;i*i<=n;i+=2) {
        if(n%i==0)
            return false;
    }
    return n%2==0? false: true; }

public static void main(String args[]){
    String n="0";
    int x = Integer.parseInt(n);
    int z=x;
    int a=0;
    int i=1;
    while(!p(x)){

      a = i*(int)Math.pow(-1, i);
      i++;
      x+=a;
    }

    System.out.println( (int) Math.abs(x-z));}

this is for n>=2.

answered Nov 27, 2016 at 19:04

mikemike

414 bronze badges

In python:

>>> def nearest_prime(n):
    incr = -1
    multiplier = -1
    count = 1
    while True:
        if prime(n):
            return n
        else:
            n = n + incr
            multiplier = multiplier * -1
            count = count + 1
            incr = multiplier * count

>>> nearest_prime(3)
3
>>> nearest_prime(4)
3
>>> nearest_prime(5)
5
>>> nearest_prime(6)
5
>>> nearest_prime(7)
7
>>> nearest_prime(8)
7
>>> nearest_prime(9)
7
>>> nearest_prime(10)
11

answered Mar 8, 2017 at 14:01

<?php
$N1Diff = null;
$N2Diff = null;

$n1 = null;
$n2 = null;

$number = 16;

function isPrime($x) {

    for ($i = 2; $i < $x; $i++) {
        if ($x % $i == 0) {
            return false;
        }
    }

    return true;
}


for ($j = $number; ; $j--) {

    if( isPrime($j) ){
       $N1Diff = abs($number - $j);
       $n1 = $j;
       break;
    }
}


for ($j = $number; ; $j++) {

    if( isPrime($j) ){
       $N2Diff = abs($number - $j);
       $n2 = $j;
       break;
    }

}

if($N1Diff < $N2Diff) {

    echo $n1;

} else if ($N1Diff2 < $N1Diff ){
    echo $n2;
}

answered Aug 21, 2017 at 11:57

If you want to write an algorithm, A Wikipedia search for prime number led me to another article on the Sieve of Eratosthenes. The algorithm looks a bit simple and I’m thinking a recursive function would suit it well imo. (I could be wrong about that.)

answered Oct 15, 2009 at 21:30

ZackZack

2,4884 gold badges37 silver badges50 bronze badges

If the array solution isn’t a valid solution for you (it is the best one for your scenario), you can try the code below. After the “2 or 3” case, it will check every odd number away from the starting value until it finds a prime.

static int NearestPrime(double original)
{
    int above = (int)Math.Ceiling(original);
    int below = (int)Math.Floor(original);

    if (above <= 2)
    {
        return 2;
    }

    if (below == 2)
    {
        return (original - 2 < 0.5) ? 2 : 3;
    }

    if (below % 2 == 0) below -= 1;
    if (above % 2 == 0) above += 1;

    double diffBelow = double.MaxValue, diffAbove = double.MaxValue;

    for (; ; above += 2, below -= 2)
    {
        if (IsPrime(below))
        {
            diffBelow = original - below;
        }

        if (IsPrime(above))
        {
            diffAbove = above - original;
        }

        if (diffAbove != double.MaxValue || diffBelow != double.MaxValue)
        {
            break;
        }
    }

    //edit to your liking for midpoint cases (4.0, 6.0, 9.0, etc)
    return (int) (diffAbove < diffBelow ? above : below);
}

static bool IsPrime(int p)  //intentionally incomplete due to checks in NearestPrime
{
    for (int i = 3; i < Math.Sqrt(p); i += 2)
    {
        if (p % i == 0)
            return false;
    }

    return true;
}

answered Oct 15, 2009 at 22:06

Austin SalonenAustin Salonen

48.9k15 gold badges108 silver badges139 bronze badges

Lookup table whit size of 100 bytes; (unsigned chars)
Round real number and use lookup table.

answered Oct 18, 2009 at 20:28

Luka RahneLuka Rahne

10.3k3 gold badges33 silver badges56 bronze badges

Maybe we can find the left and right nearest prime numbers, and then compare to get the nearest one. (I’ve assumed that the next prime number shows up within next 10 occurrences)

def leftnearestprimeno(n):
    n1 = n-1
    while(n1 >= 0):
        if isprime(n1):
            return n1
        else:
            n1 -= 1
    return -1

def rightnearestprimeno(n):
    n1 = n+1
    while(n1 < (n+10)):
        if isprime(n1):
            return n1
        else:
            n1 += 1

    return -1


n = int(input())
a = leftnearestprimeno(n)
b = rightnearestprimeno(n)
if (n - a) < (b - n):
    print("nearest: ", a)
elif (n - a) > (b - n):
    print("nearest: ", b)
else: 
    print("nearest: ", a)        #in case the difference is equal, choose min 
                                 #value

answered Aug 24, 2020 at 20:47

valkyrie55valkyrie55

3253 silver badges10 bronze badges

Simplest answer-
Every prime number can be represented in the form (6*x-1 and 6*X +1) (except 2 and 3).
let number is N.divide it with 6.
t=N/6;
now
a=(t-1)*6
b=(t+1)*6
and check which one is closer to N.

answered Apr 29, 2016 at 7:04

Источник

Ближайшее простое

20.09.2022, 00:50. Показов 1367. Ответов 21

Здравствуйте, помогите пожалуйста исправить(доработать код) или написать новый, как кому будет удобно с++ – python.

Python

from itertools import count
 
def prime(n):
    for i in range(2, (n // 2) + 1):
        if n % i == 0:
            return False
    else:
        return True
 
def prime_closest_to(n):
    for i in count(n):
        if prime(i):
            x = i
            dx = x - n
            break
    for j in count(n - 1, 1):
        if prime(j):
            y = j
            dy = n - y
            break
    ret = x if dx < dy else y
    return ret
 
n = int(input())
print(prime_closest_to(n))

1 WA 0 0,000 2 740,0k
2 OK 4,80 0,000 2 752,0k
3 OK 4,80 0,000 2 704,0k
4 OK 4,80 0,000 2 724,0k
5 OK 4,80 0,001 2 756,0k
6 OK 4,80 0,000 2 704,0k
7 OK 4,80 0,000 2 792,0k
8 OK 4,80 0,000 2 788,0k
9 OK 4,80 0,000 2 736,0k
10 OK 4,80 0,000 2 744,0k
11 OK 4,80 0,001 2 752,0k
12 OK 4,80 0,001 2 736,0k
13 WA 0 0,000 2 788,0k
14 WA 0 0,000 2 776,0k
15 OK 4,80 0,000 2 744,0k
16 TL 0 0,203 2 788,0k
17 TL 0 0,204 2 808,0k
18 TL 0 0,203 2 796,0k
19 OK 4,80 0,000 2 744,0k
20 TL 0 0,205 2 728,0k

Вердикт Опис вердикту
OK
Accepted. Рішення успішно відпрацювало на вказаному тесті. Якщо такий вердикт отримано на всіх тестах, це означає, що ви повністю вирішили завдання.

CE
Compilation Error. Помилка компіляції. Компілятор не створив файл, що виконується. Вам надається повне виведення компілятора. Можливі причини: синтаксична помилка в програмі, при відправці була вказана неправильна мова програмування.

PE
Presentation Error. Неправильний формат виводу. На вказаному тесті програма виводить дані, які не відповідають умові завдання. Можливі причини: програма виводить у вихідні дані сторонній текст; програма виводить недостатню кількість вихідних даних; використовується файлове введення/виведення і вихідний файл вказаний у програмі неправильно; вихідні дані взагалі створюються.

WA
Wrong Answer. На цьому тесті ваше рішення видає неправильну відповідь. Можливі причини: реалізований неправильний алгоритм, відбулося переповнення в цілісній змінній, речові значення виводяться з недостатньою точністю.

TL
Time Limit Exceeded. На цьому тесті перевищено час виконання програми, тобто. ваша програма працює довше, ніж допустимо для цього завдання. Можливі причини: алгоритм через помилку входить до безкінечного циклу; написаний алгоритм розв’язання задачі має неправильну асимптотику, тобто є неоптимальним та його треба спробувати покращити.

ML
Memory Limit Exceeded. На зазначеному тесті перевищено огранічні пам’яті, тобто. Ваша програма вимагає більше оперативної пам’яті, ніж допустимо для цього завдання. Можливі причини: алгоритм використовує великі структури даних; в алгоритмі відбувається дуже багато рекурсивних викликів.

RE
Runtime Error. На вказаному тесті програма неправильно завершила роботу, іншими словами, сталася помилка під час виконання програми. Можливі причини: розподіл на нуль, вилучення кореня квадратного з негативного числа, звернення до неіснуючих елементів масиву чи рядка тощо.

FF
Forbiden Function. Заборонена функція. На вказаному тесті програма викликала одну з функцій, яка може порушити роботу системи тестування.

Миниатюры

Источник

Как найти ближайшее простое число?

есть ли хороший алгоритм, чтобы найти ближайшее простое число к заданному real номер? Мне нужно искать только в пределах первых 100 простых чисел или около того.

в настоящее время у меня есть куча простых чисел, хранящихся в массиве, и я проверяю разницу по одному числу за раз (O(n)?).

13 ответов

вместо отсортированного списка простых чисел, учитывая относительно небольшой целевой диапазон, есть массив, индексированный всеми нечетными числами в диапазоне (вы знаете, что нет четных простых чисел, кроме частного случая 2) и содержащий ближайшее простое число. Поиск решения становится O (1) по времени.

Я думаю, что 100-й Прайм-это около 541. массив из 270 [малых] ints-это все, что нужно.

этот подход особенно актуален, учитывая относительно высокую плотность простых чисел (в частности относительно нечетных чисел), в диапазоне ниже 1000. (Как это влияет на размер двоичного дерева)

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

Edit: учитывая распределение простых чисел в этом диапазоне, вы, вероятно, могли бы ускорить (немного), используя интерполяционный поиск – вместо того, чтобы всегда начинать с середины таблицы, используйте линейную интерполяцию, чтобы угадать больше точная отправная точка. 100-е простое число должно быть где-то около 250 или около того (на предположение-я не проверял), поэтому, если (например) вы хотите, чтобы он был ближе к 50, вы бы начали около 1/5 пути в массив, а не на полпути. Вы можете в значительной степени рассматривать простые числа как начинающиеся с 1, поэтому просто разделите число, которое вы хотите, на наибольшее в вашем диапазоне, чтобы получить догадку в начальной точке.

ответы до сих пор довольно сложным, учитывая задачи. Первая сотня простых чисел!–3–> – все меньше 600. Я бы создал массив размером 600 и поместил в каждом значение ближайшего простого числа к этому числу. Затем, учитывая номер для тестирования, я бы округлил его вверх и вниз, используя floor и ceil функции для получения одного или двух ответов кандидата. Простое сравнение с расстояниями до этих чисел даст вам очень быстрый ответ.

самым простым подходом было бы сохранить простые числа в отсортированном списке и изменить алгоритм для выполнения двоичного поиска.

стандартный алгоритм двоичного поиска вернет null для промаха, но он должен быть прямым, чтобы изменить его для ваших целей.

самый быстрый алгоритм? Создайте таблицу поиска с элементами p[100]=541 и верните результат для floor(x) со специальной логикой для x на [2,3]. Это будет O(1).

вы должны отсортировать свой номер в массиве, тогда вы можете использовать бинарный поиск. Этот алгоритм имеет производительность O(log n) в худшем случае.

public static boolean p(int n){

    for(int i=3;i*i<=n;i+=2) {
        if(n%i==0)
            return false;
    }
    return n%2==0? false: true; }

public static void main(String args[]){
    String n="0";
    int x = Integer.parseInt(n);
    int z=x;
    int a=0;
    int i=1;
    while(!p(x)){

      a = i*(int)Math.pow(-1, i);
      i++;
      x+=a;
    }

    System.out.println( (int) Math.abs(x-z));}

это для n>=2.

в python:

>>> def nearest_prime(n):
    incr = -1
    multiplier = -1
    count = 1
    while True:
        if prime(n):
            return n
        else:
            n = n + incr
            multiplier = multiplier * -1
            count = count + 1
            incr = multiplier * count

>>> nearest_prime(3)
3
>>> nearest_prime(4)
3
>>> nearest_prime(5)
5
>>> nearest_prime(6)
5
>>> nearest_prime(7)
7
>>> nearest_prime(8)
7
>>> nearest_prime(9)
7
>>> nearest_prime(10)
11

автор: Arindam Roychowdhury

<?php
$N1Diff = null;
$N2Diff = null;

$n1 = null;
$n2 = null;

$number = 16;

function isPrime($x) {

    for ($i = 2; $i < $x; $i++) {
        if ($x % $i == 0) {
            return false;
        }
    }

    return true;
}


for ($j = $number; ; $j--) {

    if( isPrime($j) ){
       $N1Diff = abs($number - $j);
       $n1 = $j;
       break;
    }
}


for ($j = $number; ; $j++) {

    if( isPrime($j) ){
       $N2Diff = abs($number - $j);
       $n2 = $j;
       break;
    }

}

if($N1Diff < $N2Diff) {

    echo $n1;

} else if ($N1Diff2 < $N1Diff ){
    echo $n2;
}

Если вы хотите написать алгоритм, поиск в Википедии простое число привел меня к другой статье о решето Эратосфена. Алгоритм выглядит немного простым, и я думаю, что рекурсивная функция подойдет ему хорошо imo. (Тут я могу ошибаться.)

Если решение массива не является допустимым решением для вас (это лучшее решение для вашего сценария), вы можете попробовать код ниже. После случая “2 или 3″он будет проверять каждое нечетное число от начального значения, пока не найдет простое.

static int NearestPrime(double original)
{
    int above = (int)Math.Ceiling(original);
    int below = (int)Math.Floor(original);

    if (above <= 2)
    {
        return 2;
    }

    if (below == 2)
    {
        return (original - 2 < 0.5) ? 2 : 3;
    }

    if (below % 2 == 0) below -= 1;
    if (above % 2 == 0) above += 1;

    double diffBelow = double.MaxValue, diffAbove = double.MaxValue;

    for (; ; above += 2, below -= 2)
    {
        if (IsPrime(below))
        {
            diffBelow = original - below;
        }

        if (IsPrime(above))
        {
            diffAbove = above - original;
        }

        if (diffAbove != double.MaxValue || diffBelow != double.MaxValue)
        {
            break;
        }
    }

    //edit to your liking for midpoint cases (4.0, 6.0, 9.0, etc)
    return (int) (diffAbove < diffBelow ? above : below);
}

static bool IsPrime(int p)  //intentionally incomplete due to checks in NearestPrime
{
    for (int i = 3; i < Math.Sqrt(p); i += 2)
    {
        if (p % i == 0)
            return false;
    }

    return true;
}

таблица поиска с размером 100 байт; (беззнаковые символы)
Круглое реальное число и используйте таблицу поиска.

самый простой ответ-
Каждое простое число может быть представлено в виде (6*x-1 и 6 * X +1) (кроме 2 и 3).
пусть число N. разделите его на 6.
t=N / 6;
сейчас
a=(t-1)*6
b=(t+1)*6
и проверить, какой из них ближе к Н.

Источник

Мог вносит много изменений, но какие из них вы должен вносите, зависит от того, чего вы хотите добиться. Самая большая проблема с вашим кодом в его нынешнем виде заключается в том, что вы успешно идентифицируете простые числа с помощью break, а затем ничего не делаете с этой информацией. Вот минимальное изменение, которое делает примерно то же самое.

def get_nearest_prime(old_number):
    largest_prime = 0
    for num in range(old_number + 1, 2 * old_number) :
        for i in range(2,num):
            if num % i == 0:
                break
        else:
            largest_prime = num
    return largest_prime

Мы используем локальную переменную largest_prime, чтобы отслеживать все найденные простые числа (поскольку вы выполняете итерацию по ним в возрастающем порядке). Предложение else запускается каждый раз, когда вы выходите из внутреннего цикла for “в обычном режиме” (т. Е. Без попадания в предложение break). Другими словами, каждый раз, когда вы находите лучшее.

Вот немного более быстрое решение.

import numpy as np

def seive(n):
    mask = np.ones(n+1)
    mask[:2] = 0
    for i in range(2, int(n**.5)+1):
        if not mask[i]:
            continue
        mask[i*i::i] = 0
    return np.argwhere(mask)

def get_nearest_prime(old_number):
    try:
        n = np.max(seive(2*old_number-1))
        if n < old_number+1:
            return None
        return n
    except ValueError:
        return None

Он делает примерно то же самое, но использует алгоритм, называемый «Решетом Эратосфена», для ускорения поиска простых чисел (в отличие от «пробного деления», которое вы используете). Это не самое быстрое сито в мире, но его можно понять без особых настроек.

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

Примечание, что я не уверен, что указанный вами диапазон всегда содержит простое число. Это вполне может быть, и если это так, вы можете обойтись намного более коротким кодом. Примерно так.

def get_nearest_prime(old_number):
    return np.max(seive(2*old_number-1))

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

Источник

← →
r@bbit

(2006-07-23 17:07)
[0]

Народ, помогите плиз! Требуется найти ближайшее простое число к заданному N (WORD), перебрать числа в прямом и обратном от N порядке не проблема, но как быстро и правильно определить простое ли оно? Вопрос туповат конечно, но раньше такого не делал, изобретать изобретённое неохота – лаба того не стоит. Нужен принцип определения простое ли число. Попроще принцип, если можно 🙂 Заранее благодарен.

← →
Palladin ©

(2006-07-23 17:23)
[1]

попроще? без проблемм 🙂

Function IsSimple(n:Integer):Boolean;
Var
i:Integer;
Begin
Result:=False;
For i:=2 to n-1 Do If (n mod i)=0 Then Exit;
Result:=True;
End;

← →
Palladin ©

(2006-07-23 17:25)
[2]

или еще лучше
For i:=2 to (n div 2)

← →
r@bbit

(2006-07-23 18:52)
[3]

>Palladin
сенькс! вообще я предполагал, что делений будет поменьше… а так получается цикл до N div 2. хммм… то есть если число скажем 1000 то делений будет около 500…

← →
Ketmar ©

(2006-07-23 19:03)
[4]

>r@bbit (23.07.06 18:52) [3]
для тысячи будет ровно одно. %-)

← →
Desdechado ©

(2006-07-23 19:35)
[5]

Ketmar © (23.07.06 19:03) [4]
Нет. Ему ж найти ближайшее простое (видимо, в обе стороны), а не выяснить, простое ли данное.

← →
Palladin ©

(2006-07-23 19:52)
[6]

> Desdechado © (23.07.06 19:35) [5]

В смысле нет? для 1000 будет именно одно… только на 2. А вот для 1009 будет аж 504.

← →
Desdechado ©

(2006-07-23 20:04)
[7]

> для 1000 будет именно одно..
Это для выяснения, что 1000 – не простое. А для поиска ближайшего простого сколько итераций?

← →
Palladin ©

(2006-07-23 20:22)
[8]

> Desdechado © (23.07.06 20:04) [7]

в [3] имелось в виду именно проверка

← →
Vendict ©

(2006-07-23 20:25)
[9]

r@bbit (23.07.06 17:07) [0]
я думаю стоит просто проверить на простоту числа +/-20 к примеру и найти ближайшее.
есть вероятностные методы с меньшей сложностью, чем деление на всё что меньше:

http://algolist.manual.ru/maths/teornum/
http://algolist.manual.ru/maths/teornum/rabmil.php
и генерация http://algolist.manual.ru/maths/teornum/gene_prime.php

← →
Lamer@fools.ua ©

(2006-07-23 21:43)
[10]

Palladin © (23.07.06 17:25) [2]

>или еще лучше
>For i:=2 to (n div 2)

Лучше, IMHO, всё-таки хотя бы так:
function IsPrime(n: Cardinal): Boolean; var i, maxI: Cardinal; begin Result := False; if not Odd(n) and (n > 2) then Exit; maxI := Trunc(Sqrt(n)); i := 3; while i <= maxI do begin if n mod i = 0 then Exit; Inc(i, 2); end; Result:=True; end;

WORD это 65536 значений
на каждое значение – единственное ближайшее простое число(если так вышло, что для какого-то числа два ближайших простых, выбрать по какому-либо правилу – одно)
я к тому, что можно один раз посчитать для всех значений простые числа и потом использовать готовый результат, если памяти не жалко и есть её
есть ещё идея – посчитай для всех значений простых чисел и внимательно присмотрись
очень вероятно, что можно увидеть какие-либо закономерности нахождения ближайших простых чисел для первых 65536 чисел, на основе замеченного вполне возможно удастся очень даже заметно сократить перебор это если без хранения всего в памяти обходиться

+[11]
“посчитай для всех значений простых чисел “–>посчитай для всех значений ближайшие простые числа
“и внимательно присмотрись”
тут я малость погорячился, ибо 65536 чисел для человека – необозримая совокупность
самое очевидное, можно найти максимальное расстояние на котором может находиться от заданного числа его ближайшее простое число, чтобы сократить перебор
можно проверить другие эвристики(догадки) относительно возможных закнономерностей(в цикле конечно, взглядом закономерность тут не подметить)
это если конечно – скорость критична, а память использовать нельзя по каким-либо причинам

default © (23.07.06 22:36) [12]
а память использовать нельзя по каким-либо причинам
сложно представить себе ситуацию при которой было бы жалко 13 кило единовременно выделить..

Корень из 65536 = 256. Число простых чисел до 256 – весьма мало. Порядка 46 штук. И находятся весьма быстро с тем же решетом. После этого найти ближайшее к любому вне этого ряда до 256 – дело техники.

На algolist.manual.ru есть несколько алгоритмов. Хотя бля лабы действительно многовато.

Не претендуя на откровение положу-ка я тут наивный код. На диапазоне 2..high(word) подготовка времени не занимает вообще, а поиск – будет хорошо работать в любом диапазоне.

program n; {$apptype console} uses SysUtils;


var Ar: array of word;
    Cn: integer;
 procedure Add (N: word);
 begin
   inc (Cn);
   if Cn > length (Ar) then
     SetLength (Ar, Cn * 2);
   Ar[Cn - 1] := N;
 end;
 function IsSimple (N: word): boolean;
 var i: integer;
     q: double;
 begin
   result := true;
   q := sqrt (N);
   for i := 0 to Cn - 1 do
     if Ar[i] > q then
       exit
       else
     if (N mod Ar[i]) = 0 then begin
       result := false;
       exit;
       end;       
 end;
 function Nearest (N: word; var R: word): boolean;
 var l, h, m: integer;
 begin
   l := 0; h := Cn - 1;
   if L >= h then begin
     result := false;
     exit;
     end;
   result := true;
   repeat
     m := (l + h) shr 1;
     if Ar[m] < N then
       l := m + 1
       else
       h := m - 1;       
   until l > h;
   R := Ar[m];
   if m > 0 then
     if abs (R - N) > abs (Ar[m-1] - N) then
       R := Ar[m - 1];
   if m < Cn then
     if abs (R - N) > abs (Ar[m+1] - N) then
       R := Ar[m + 1];
 end;
var i, j: word;
    s: string;
begin
  Cn := 0;
    writeln ("Preparing");
  Add (2);
  for i := 3 to high (word) do
    if IsSimple (i) then
      Add (i);
  writeln;
  repeat
    write ("Enter a number: ");
    readln (s);
    try
     i := StrToInt (s);
     if Nearest (i, j) then
       writeln ("The nearest simple number for ", i, " is ", j)
       else
       writeln ("The nearest number for ", i, " was not found");
    except
      writeln ("error");
    end;
  until false;
end.

Думкин © (24.07.06 6:34) [14]
Корень из 65536 = 256. Число простых чисел до 256 – весьма мало. Порядка 46 штук. И находятся весьма быстро с тем же решетом. После этого найти ближайшее к любому вне этого ряда до 256 – дело техники.
А если ближайшее – сильное простое ? (т.е. (n-1)2=0 если n простое) то придтся периберать до (n div 2) или как-то ещё изворачиваться. не проще проверить одним из алгоритмов числа +-20 ?

> Vendict © (24.07.06 21:34) [18]

Извиняюсь за свой английский в предыддущем посте – комп переклинило и не хотел переключаться на русское. Перегрузился.
Так вот, если не затруднит, то проясните мне следующее:
1. Что есть сильное простое?
2. Причем тут изворачиваться?
3. Почему ваш алгоритм быстрее?

1. p – сильное простое, если (p-1) имеет большой простой делитель.
2. придётся или искать числа до р/2 или проверять при методе пробного деления, простое ли число осталось.
3. Алгоритм генерации простых чисел около O(n div 2) тот алгоритм, который проверяет число на простоту порядка O(m), где m – количество проверок, такое что 0.5^m достаточно близко к 0лю.

И я думаю лаба и нацелена на использование вероятностных алгоритмов проверки на простоту.
И вдруг у нас не Word а LongWord, то скорость будет заметна.

> Vendict © (25.07.06 19:36) [21]
> 1. p – сильное простое, если (p-1) имеет большой простой
> делитель

насколько большой? что значит большой?

← →
SergP.

(2006-07-25 19:59)
[24]

Это еще не самый лучший вариант…

StriderMan © (25.07.06 19:38) [23]
насколько большой? что значит большой?
“сильное простое” данный термин используется в криптографии как я написал “p – сильное простое, если (p-1) имеет большой простой делитель.” логично, имеется ввиду больше корня из p.

> Vendict ©

Значит вы просто не прочитали то, что предложил я. Ну и безусловно – не вникли. А вы попробуйте и заберите свои слова назад. У вас получится, если постараетесь. Это еще Роллинги утверждали.

> Vendict © (25.07.06 20:18) [25]

Раз оно имеет такой большой делитель, то по логике оно должно иметь и меньший. Дойдя до оного и поймем – что число не простой. В чем загвоздка?

318-225-800

> Дойдя до оного и поймем – что число не простоe.

Конечно, не простое. Если p – большое простое, то p-1 – не только не простое, оно четное. А “сильное” простое число ищут, чтобы затруднить попытки разложения на множители некоторым вероятностным алгоритмом, который как раз плохо работает для таких сильных простых. Подробности я не знаю, но в книжках об этом пишут.

> palva © (26.07.06 11:04) [31]

То что оно четное – это ясно. 🙂
Но каким боком это относится к написаному мной – лично я так и не увидел. 🙂

> palva © (26.07.06 11:17) [33]

Вы поняли правильно. Но я принял данное выше определение “сильного простого”. А вот каким боком оно усложнит предложенный мной метод – не увидел. После нахождения массива первых простых чисел, каждая проверка числа на простоту потребует в худшем варанте порядка n^0.5/ln(n^0.5) нахождений остатков, что значительно лучше чем (n div 2).

Ведь тепатировать можно, что угодно в том числе и такое:

> И я думаю лаба и нацелена на использование вероятностных
> алгоритмов проверки на простоту.

А к чему?

К тому же для нахождения этих чисел до 256 достаточно провести расчеты с 2,3,5,7,11,13. И даже в случае с LongWord все не так грустно. Массив будет порядка 6000 элементов.

Источник

Ближайшее простое

Как найти ближайшее простое число?

13 ответов

Вам также может понравиться

Как найти работу лампы физика

Как исправить ошибки в гугл таблице

Как найти песню без программ

Добавить комментарий Отменить ответ