Получить таблицу простых чисел во время компиляции

#cpp #шаблоны_с++ #простые_числа

Говорят, что шаблонное программирование началось с вычисления простых чисел. Так
что компилятор их точно может вычислить во время компиляции.
И даже я худо-бедно могу написать или переписать такой шаблон:

template
struct DoIsPrime {
    static constexpr bool value = (p%d != 0) && DoIsPrime::value;
    };

template
struct DoIsPrime {
    static constexpr bool value = (p % 2 != 0);
    };

template
struct IsPrime {
    static constexpr bool value = DoIsPrime < p, p / 2 >::value;
    };

template<>
struct IsPrime<0> {
    static constexpr bool value = false;
    };
template<>
struct IsPrime<1> {
    static constexpr bool value = false;
    };
template<>
struct IsPrime<2> {
    static constexpr bool value = true;
    };
template<>
struct IsPrime<3> {
    static constexpr bool value = true;
    };

template
bool isPrime = IsPrime
::value;


А как бы их еще и сохранить? как теперь записать таблицу простых чисел во время компиляции?
Скажем, получить

unsigned int p[] = { }


где p[i] - просто простые числа до какой-то границы? p[0]=2, p[1]=3 и так далее?
    

Ответы

Ответ 1

Воспользуюсь вашими наработками в своем ответе:

//Ваш код проверки на простоту выше
template
constexpr bool isPrime = IsPrime
::value;  //Этот тоже ваш, просто добавил constexpr  

template
struct PrimeAray;

template
struct PrimeAray : PrimeAray, numbers..., number>{

};

template
struct PrimeAray : PrimeAray, numbers...>{

};

template
struct PrimeAray<0, number, true, numbers...>{
    static const int arr[];
};

template
const int PrimeAray<0, number, true, numbers...>::arr[] = {numbers...};

int main(){
    for(int i : PrimeAray<10>::arr){
        std::cout << i << std::endl;
    }
}


На экране будет 10 простых чисел. 

Теперь что же здесь творится. Рекурсивно инстанцируем и наследуем шаблон PrimeAray.
На каждом шаге увеличиваем проверяемое число на 1. Если число простое, добавляем его
в список и уменьшаем заданное количество на 1. Когда количество станет равно 0, значит
все необходимые простые числа найдены и можно положить результат в массив и прерывать
рекурсию. 

Полный пример


Ответ 2

Вариант 1

Получаем массив простых чисел, встретившихся до заданного целого числа.

online compiler :

#include 
#include 
#include 

// Перебираем числа вплоть до заданного, складывая простые в массив.
template<::std::uint32_t value_upper_bound> constexpr auto
Collect_Primes_Impl(void)
{
    static_assert(0 < value_upper_bound);
    ::std::array<::std::uint32_t, value_upper_bound> primes{};
    primes[0] = 1;
    ::std::uint32_t primes_count{1};
    ::std::uint32_t value{1};
    while(value_upper_bound != value)
    {
        ++value;
        bool is_prime{true};
        ::std::uint32_t prime_index{1};
        while(primes_count != prime_index)
        {
            if(0 == (value % primes[prime_index]))
            {
                is_prime = false;
                break;
            }
            ++prime_index;
        }
        if(is_prime)
        {
            primes[primes_count] = value;
            ++primes_count;
        }
    }
    return ::std::make_pair(primes_count, primes);
}

// Компонуем массив простых чисел, подгоняя под надлежащий размер.
// По идее, требуемый размер можно посчитать заранее, но тогда
// придется их вычислять по два раза.
template<::std::uint32_t value_upper_bound> constexpr auto
Collect_Primes(void)
{
    static_assert(0 < value_upper_bound);
    constexpr const auto collected{Collect_Primes_Impl()};
    ::std::array<::std::uint32_t, collected.first> primes{};
    ::std::uint32_t prime_index{0};
    while(collected.first != prime_index)
    {
        primes[prime_index] = collected.second[prime_index];
        ++prime_index;
    }
    return primes;
}

constexpr const auto pr20{Collect_Primes<20>()};

static_assert(::std::size_t{9} == pr20.size());

static_assert(::std::uint32_t{ 1} == pr20[0]);
static_assert(::std::uint32_t{ 2} == pr20[1]);
static_assert(::std::uint32_t{ 3} == pr20[2]);
static_assert(::std::uint32_t{ 5} == pr20[3]);
static_assert(::std::uint32_t{ 7} == pr20[4]);
static_assert(::std::uint32_t{11} == pr20[5]);
static_assert(::std::uint32_t{13} == pr20[6]);
static_assert(::std::uint32_t{17} == pr20[7]);
static_assert(::std::uint32_t{19} == pr20[8]);


Вариант 2

Получаем массив простых чисел заданной длины.

online compiler

template<::std::size_t primes_count, typename TInt = ::std::uint64_t> constexpr auto
Collect_Primes(void)
{
    static_assert(0 < primes_count);
    ::std::array primes{};
    primes[0] = 1;
    ::std::size_t collected_primes_count{1};
    TInt value{1};
    constexpr const TInt max_value{::std::numeric_limits::max()};
    while(max_value != value)
    {
        ++value;
        bool is_prime{true};
        ::std::size_t prime_index{1};
        while(collected_primes_count != prime_index)
        {
            if(0 == (value % primes[prime_index]))
            {
                is_prime = false;
                break;
            }
            ++prime_index;
        }
        if(is_prime)
        {
            primes[collected_primes_count] = value;
            ++collected_primes_count;
            if(primes_count == collected_primes_count)
            {
                break;
            }
        }
    }
    return primes;
}

Переполнение типа данных в тесте Ферма на простоту

#c_sharp #алгоритм #простые_числа

Добрый день. Реализовал вероятностный алгоритм определение простоты числа на основе
малой теоремы Ферма. Однако, есть проблема, что тип при даже 11-значном числе, переполняется.
Вопрос как можно элегантно решить эту проблему не используя BigInteger? 
Сам метод

public static ulong IsPrimeNumb(ulong n, ulong a)
    {
        ulong e = 1, b=a;
        for (var i = n; i > 0;)
        {
            if (i % 2 == 1)
            {
                e = (e * b) % n;                    
            }

            b = (b * b) % n;
            i /= 2;
        }
        return e == a ? n : 0; 
    }

    

Ответы

Ответ 1

e = (e * b) % n;
b = (b * b) % n;



  Произведение чисел  при делении на некоторое число дает тот же
  остаток, что и произведение их остатков.
  
  Например, посчитаем остаток 107*207 по модулю 4. Числа 107 и 207 при
  делении на 4 дают  остаток 3, если перемножить эти остатки получится
  9. А 9 при делении на 4 дает остаток 1, значит,  и 107*207 дает остаток 1.


e = ((e % n) * (b % n)) % n;
b = ((b % n) * (b % n)) % n;


Теперь переполнения быть не должно.
Что касается типов данных, то можно использовать decimal, если тебе просто не хватает
разрядов для входных значений.

Количество чисел n, у которых число делителей равно числу делителей n+1

#c_sharp #алгоритм #простые_числа #факторизация

Сама задача на первый взгляд кажется довольно простой:


  Найти количество таких чисел n (n<10^5), у которых число делителей равно числу
делителей числа n+1


Вот мое решение:  

static int NumberOfDividers(int number)
        {
            int counter = 0;
            for (int i = 1; i <= number; i++)
                if (number % i == 0)
                    counter++;
            return counter;

        }
        static void Main()
        {
            int counter = 0;
            for (int i = 1; i < 100000; i++)
            {
                if (NumberOfDividers(i) == NumberOfDividers(i + 1))
                    counter++;
            }
            Console.WriteLine(counter);
        }


Но алгоритм работает очень долго, какие есть варианты для его упрощения?
    

Ответы

Ответ 1

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

void Main()
{
    int counter = 0;
    int current = 0;
    for (int i = 1; i < 100000; i++)
    {
        int next = NumberOfDividers(i);
        if (current == next)
        {
            counter++;
        }
        current = next;
    }
    Console.WriteLine(counter);//10585 
}


Только это изменение уменьшит время работы вдвое.

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

Любое число делится на 1 и себя, поэтому сразу запишем 2 в счетчик, или 0, если это
единица.

static int NumberOfDividers(int number)
{
    int counter = number == 1 ? 0 : 2;


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

    double root = Math.Sqrt(number);


Если число является квадратом, то один из делителей будет равен корню, проверяем
и добавляем единицу в счетчик остальные делители парные. Для проверки нужна только
целая часть корня, иначе при сравнении мы никогда не получим равенства (см. этот вопрос-ответ).
Кроме того, если исходное число - единица, эта проверка добавит в счетчик ее единственный
делитель и функция вернет 1, как и должна.

    int intRoot = (int)root;
    if(intRoot * intRoot  == number)
        counter++;


Остался основной цикл. Начинаем с 2, т.к. единица и само число уже учтены. Делители
ходят парами, поэтому счетчик увеличиваем на 2. Исключением является корень из числа,
но его мы уже учли.

    for (int i = 2; i < root; i++)
        if (number % i == 0)
        {
            counter +=2;//делители ходят парами. поэтому увеличиваем сразу на два.
        }
    return counter;
}


После всех манипуляций суммарное время выполнения, по грубым замерам*, уменьшилось
с ~3 минут до ~0,4 секунды. Т.е. примерно в 450(!) раз.



*стандартный тестовый стенд не собирал, данные со встроенного счетчика времени LiNQPad


Ответ 2

Я прошу прощения, но на C# пас. Зато могу набросать на C++ :)

Итак, чтобы посчитать количество делителей - раскладываем число на простые сомножители;
количество делителей после этого определяется как... как в этом ответе :) - там расписано.

Искать делители просто - достаточно проверять простые числа до квадратного корня
из числа, причем само число всякий раз уменьшаем делением на найденный простой делитель
- для скорости. Быстрый квадратный корень передираем у Уоррена в "Алгоритмических трюках";
но можно использовать и обычный sqrt.

Считаем для каждого числа один раз, запоминая значение для предыдущего числа. 

Все, собирая все вместе - 

#include 
#include 
#include 

Нахождение всех множителей большого числа в заданном диапазоне

#cpp #алгоритм #простые_числа

Есть непростое число где-то между 796200000 и 796400000, какой есть наиболее быстрый
способ найти все его делители? (в идеале с реализацией) (нужны именно делители, для
последующего их использования)

Нет, в гугле меня не забанили, но я не смог быстро разобраться в невероятном разнообразии
алгоритмов.

Заранее спасибо.
    

Ответы

Ответ 1

Ну, как мне кажется - найти разложение на простые множители, а затем находить все
возможные сочетания простых сомножителей в непростые.

Чтобы найти все простые, достаточно проверить делимость на простые, не большие 28284
(квадратный корень из максимального числа). Чтобы найти все простые - можно заранее
то же решето Эратосфена использовать, с проверкой до 168 (очередной квадратный корень).

Что-то типа

vector primus(int max)
{
    vector p { 2 };
    vector prime(max+1, true);
    prime[0] = prime[1] = false;
    for(int i = 3; i<= max; i += 2)
        if (prime[i])
        {
            p.push_back(i);
            if (i*i <= max)
                for(int j= i*i; j <= max; j+=i)
                    prime[j] = false;
        }
    return p;
}

int main(int argc, const char * argv[])
{
    vector p = primus(28300);

    int N = 796400000;
    for(size_t i = 0; i < p.size() && N > p[i]; ++i)
    {
        while (N%p[i] == 0)
        {
            cout << p[i] << endl;
            N /= p[i];
        }
    }
    if (N > 1) cout << N << endl;
}


Окончательная полная программа получения всех (не только простых!) делителей всех
указанных чисел у меня на машине делает это за 2-3 секунды.


Ответ 2

Заранeе прогнать 200 000 чисел и составить табличку. 200 килобайт есть у всех.

P.S. Да, я знаю, что при желании можно это ужать в 8 раз, пакуя в биты

P.P.S. Да, я знаю, что если хранить все с выравниванием, получится не 200 кило, а
метр. Не страшно.


Ответ 3

Чтобы найти все делители, надо искать только делители до корня из числа, а остальные
получаются делением числа не его делитель. Осторожно обработать числа, являющиеся полными
квадратами. В общем-то всё.

http://ideone.com/akXlLV - 5К чисел за 3 секунды

vector  getDivs(int n) {
  int q;
  vector  res;

  for (q=1; q*q
Ответ 4

Разложение на множители.

#include 
#include 
using namespace std;

/*
    Функция получения делителей числа N
    N - начальное число
    &divisor - ссылка на вектор, куда запишут результат
*/
void getDivisor(int N, vector& divisor){
    int i = 2;
    while(N!=1){
        if(N % i == 0){
            N /= i;
            divisor.push_back(i);
        } else {
            ++i;
        }
    }
}

int main() {
    int N;
    vector divisor;
    cin >> N;

    getDivisor(N, divisor);

    for(int i=0; i

Поиск совершенных чисел на определённом интервале

#c #алгоритм #математика #оптимизация #простые_числа

Дано задание: В интервале [a,b] выведите все числа, такие, что сумма их делителей,
включая единицу, и не включая само число будет равна самому числу. Или -1, если таковых
чисел в интервале нет.

Необходимо оптимизировать алгоритм поиска, таким образом чтобы программа не зависала
при работе с большими числами. Попросту, чтобы после 80 000 не сообщала Time limit
exceeded Killed. Многие типы переменных и алгоритмы я ещё не использовал, поэтому информация
по данной тематике также важна. 

#include 

int main(){
    int a, b;
    scanf("%d %d", &a, &b);

    int counter = 0;
    for(int i = a; i <= b; i++) {
        int sum = 0;
        for(int j = 1; j < i; j++) {            
            if(i % j == 0) {
                sum += j;                
            }
        }
        if(sum == i) {
           printf("%d ", i);
           counter++;
        }        
    }

    if(counter == 0) {
        printf("-1");
    }

    return 0;
}

    

Ответы

Ответ 1

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


  Disclaimer: код as is, сваяно на коленке, просто показать, как должно работать.
Со всеми тонкостями типоразмеров и прочими просьба справляться самостоятельно и меня
не трогать :)


#include 
#include 
#include 

int isOddPrime(unsigned int u)
{
    for(unsigned int i = 3; i*i <= u; i+=2)
        if (u%i == 0) return 0;
    return 1;
}

unsigned int Perfect(unsigned int p)
{
    unsigned int Mersenne = (1u << p) - 1;
    if (!isOddPrime(Mersenne)) return 0;
    return Mersenne*(1u << (p-1));
}

int main()
{
    unsigned int a, b;
    scanf("%u %u",&a,&b);
    for(unsigned int p = 2;;++p)
    {
        unsigned long long s = (1ull << (2*p-1)) - (1ull << (p-1));
        if (s > b) break;
        if (s < a) continue;
        unsigned int res = Perfect(p);
        if (res) printf("%lu\n",res);
    }
}


Вывод к нужному виду (ну, там, -1 если чисел нет и т.п.) приведите сами...

P.S. А вообще, самая правильная программа на эту тему -

#include 
#include 

unsigned long long perfs[] =
{
    6,28,496,8128,33550336,8589869056,
    137438691328,2305843008139952128
};

int main()
{
    unsigned long long a, b;
    scanf("%llu %llu",&a,&b);
    int was = 0;
    for(int i = 0; i < 8; ++i)
    {
        if (perfs[i] >= a && perfs[i] <= b)
        {
            was = 1;
            printf("%llu\n",perfs[i]);
        }
    }
    if (!was) puts("-1");
}


:)

P.P.S. Всю необходимую информацию было очень легко получить, погулявшись, например,
в Википедию.


Ответ 2

Используй алгоритм, основанный на том же подходе, что и решето Эратосфена. Сделай
массив с суммой делителей, отличных от самого числа, а потом посчитай количество подходящих
чисел.



var a = Array(1000000+1).fill(0)

for (var q=1; q

Как можно ускорить алгоритм нахождения всех простых чисел?

#java #алгоритм #простые_числа

Использую алгоритм решето Эратосфена.
Поиск в диапазоне от 2 до 10000 выполняется 280 мс.
Мне нужно найти все простые числа в диапазоне от 2 до максимального значения переменной INT.
Использовать многопоточное программирование? Оптимизировать алгоритм?

import java.util.LinkedList;
import java.util.concurrent.LinkedBlockingDeque;

public class Primes {
private long timeout = System.nanoTime();
LinkedList lprimes = new LinkedList();
LinkedList lnums = new LinkedList();
public long getTimeout() {
    return timeout;
}

public void setTimeout(long timeout) {
    this.timeout = timeout;
}

public int getCountPrimes(){
    return this.lprimes.size();
}
public void timeRun() {
    System.out.println(System.nanoTime());
    System.out.println(timeout);
    System.out.println("Время выполнения равно " + String.valueOf(System.nanoTime()
- this.timeout)+" ns или " + String.valueOf((System.nanoTime() - this.timeout)/1000000));
}

public void keepPrimes() {
    lnums.add(2);
    for(int i = 3;i <= 10000;i += 2){
           lnums.add(i);
    }
    /*for (int i = 2; i <= 10000; i++) {
        lnums.add(i);
    }*/
    while(lnums.size()>0){
        int nextPrime = lnums.remove();
        for (int i = nextPrime*nextPrime; i <=10000; i+=nextPrime) {
            lnums.removeFirstOccurrence(i);
        }
        lprimes.add(nextPrime);
        System.out.println(nextPrime);
    }
}

public static void main(String[] args) {
    // TODO Auto-generated method stub
    System.out.println("Максимальное значение INT: "+Integer.MAX_VALUE);
    Primes primes = new Primes();
    primes.keepPrimes();
    System.out.println("Формирование коллекции закончено!");
    primes.timeRun();
    System.out.println(primes.getCountPrimes());
}


}
    

Ответы

Ответ 1

Увы, я в Java не силен, разве что читать чужой код. Но...

Да, есть алгоритм решета Эратосфена O(n), но тут выигрыш по сравнению с хорошей реализацией
- O(n lg lg n) - очень небольшой. 

А вот оптимизировать ваш код не то что можно - нужно! 
Вы зачем-то собираете все нечетные числа в связанный список, а потом проверяете и
убираете их из него. Зачем? Просто проходите по всем нечетным числам в списке. И проходите
не до последнего числа (10000), а до квадратного корня! Этого достаточно. Смотрите,
любое составное число, большее корня, должно иметь делитель, меньше корня - а значит,
оно уже будет вычеркнуто. Все проверки для чисел от 100 и до 10000 просто не нужны...

И еще тоже очень большой минус - вы используете связанный список с постоянным динамическим
выделением памяти, косвенными обращениями, долгим доступом к элементам и т.п. - что
еще и не дает использовать кэш данных - решение, как по мне, нехорошее. Если бы это
был C++, я бы использовал компактный vector, заранее зарезервировав необходимое
количество памяти.

P.S. На C++ набросал - на моей домашней просчитало до 10000 за 16 мкс, до 100000000
- за 557 мс (без вывода на экран).


Ответ 2

Вывод простых чисел от 2 до 2**31-1 на C

#include 
#include 
#include 
#define lim INT32_MAX
#define BITS 32
int main()
{
    uint32_t *x= calloc(sizeof*x, ((unsigned)lim-3+BITS*2-1)/(BITS*2));
    fputs("2\n", stdout);
    for(unsigned i=3;i<=lim;i+=2) {
        unsigned b= i-3 >> 1;
        if(x[b/BITS] & 1<>1) ) x[b/BITS] |= 1<
#include 
#include 
#define lim INT32_MAX
#define BITS 32
int main()
{
    uint32_t *x= calloc(sizeof*x, ((unsigned)lim-5+BITS*3-3)/(BITS*3));
    fputs("2\n3\n", stdout);
    for(unsigned i=5, b0=0; i<=lim; i+=6, b0++) {
        unsigned b=b0;
        if(!( x[b/(BITS/2)] & 1<
Ответ 3

Заинтересовал ответ sercxjo. Поигрался немного. На моей машине его код, скомпилированный
VC++ 2015, работает (без вывода) 12 с. Там же мой вариант

#include 
#include 
#include 

constexpr inline unsigned long pow2(unsigned long i) { return 1 << i; }

unsigned long isqrt(unsigned long a)
{
    unsigned long x = a;
    for(unsigned long z = 0; x != z; )
    {
        z = x;
        x = (x + a/x)/2;
    }
    return x;
}

constexpr unsigned long MAX_LIM = pow2(31) - 1;
constexpr unsigned long ARR_LIM = (MAX_LIM >> 6) + 1;
const     unsigned long SQR_LIM = isqrt(MAX_LIM);;

unsigned long primes[ARR_LIM] = { 0 }; // 0 - простое, 1 - составное

auto set_primes = [](unsigned long idx)
    { primes[idx >> 6] |= pow2((idx&0x0000003F)>>1); };
auto get_primes = [](unsigned long idx)
    { return primes[idx >> 6] &  pow2((idx&0x0000003F)>>1); };

int main(int argc, const char * argv[])
{
    for(unsigned long i = 3; i <= SQR_LIM; i += 2)
    {
        if (get_primes(i)) continue;
        for(unsigned long j = i * i; j <= MAX_LIM; j += 2*i)
        {
            set_primes(j);
        }
    }

    puts("2");
    for(unsigned long i = 3; i <= MAX_LIM; i+=2)
    {
        if (get_primes(i)) continue;
        printf("%lu\n",i);
    }
}


считает (опять же, без вывода) 7.82 с. Результаты совпадает :)

Интересно, что если перебирать простые вида , то намечается даже проигрыш по времени...

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

Следующим номером должно быть просеивание через решето Эратосфена с использованием
шаблонов во время компиляции :) Кто готов взяться?

Наибольшее число палиндром, которое является произведением двух простых пятизначных чисел

#android #циклы #простые_числа

Делал приложение по ТЗ из одной компании. Сделал андроид-аппку, получил результат
на эмуляторе, вроде же верный. Но HR просто отписалась, что ответ который выдало мое
приложение неверен.
Айчары люди довольно занятые, потому редко кто может указать на ошибку, а навязываться
после отказа - дело очень неблагодарное. Но все же хочется хоть для себя выполнить
задание до конца.

Из требований было:


  Напишите программу, которая возвращает наибольшее число палиндром, которое
  является произведением двух простых пятизначных чисел, а также возвращает
  сами сомножители.
  Простое число - это натуральное число, которое делится нацело только на 1 и
  на себя само (2, 3, 5, 7, 11, …)
  Палиндром – строка, которая читается одинаково в обоих направлениях
  (например ABBA)


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

Потому решил использовать циклы для сопоставления и отсеивания.

Вот код моего андроид-приложения:

MainActivity:

public class MainActivity extends AppCompatActivity implements View.OnClickListener {

    private int maxNum = 99999;
    private int minNum = 10000;

    private int divNumMax = 0;
    private int palind;

    private TextView tv1;
    private TextView tv2;
    private TextView tv3;
    private TextView tv4;


    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main);

        tv1 = (TextView) findViewById(R.id.textView1);
        tv2 = (TextView) findViewById(R.id.textView2);
        tv3 = (TextView) findViewById(R.id.textView3);
        tv4 = (TextView) findViewById(R.id.textView4);

        Button btnStart = (Button) findViewById(R.id.button);
        btnStart.setOnClickListener(this);

    }

    @Override
    public void onClick(View v) {

        divNumMax = (int) Math.sqrt(maxNum);

        int fPM;
        int sPM;
        boolean isNotPalind;

        fPM = findMaxPrimeNumber(maxNum);
        sPM = findMaxPrimeNumber(fPM - 2);
        isNotPalind = findPalindrome(fPM, sPM);

        while (isNotPalind) {

            if (sPM <= fPM && sPM > minNum) {
                sPM = findMaxPrimeNumber(sPM - 2);
                isNotPalind = findPalindrome(fPM, sPM);

            } else if (sPM <= minNum) {
                fPM = findMaxPrimeNumber(fPM - 2);
                sPM = fPM;
            }

            tv2.setText("1-st primary number: " + fPM);
            tv3.setText("2-nd primary number: " + sPM);
            tv4.setText("1-st * 2-nd = " + palind);

        }
    }


    private int findMaxPrimeNumber(int maxNumPre) {
        int i;
        int j;
        int z;
        int maxNumNew;

        for (i = maxNumPre; i >= minNum; i = i - 2) {

            for (j = 3; j <= divNumMax; j++) {

                z = i % j;

                if (z == 0 && j <= divNumMax) {
                    break;

                } else if (z != 0 && j == divNumMax) {
                    maxNumNew = i;
                    return maxNumNew;

                }
            }

        }
        return 10000;
    }


    private boolean findPalindrome(int firstPrime, int secondPrime) {

        int resultOfMath = firstPrime * secondPrime;

        String ltrResult = Integer.toString(resultOfMath);
        String rtlResult = new StringBuffer(ltrResult).reverse().toString();

        if (ltrResult.equals(rtlResult)) {

            palind = resultOfMath;
            return false;

        } else {
            return true;
        }
    }
}


Скриншот полученного результата на эмуляторе:



Ломаю голову где ошибся, что упустил. Не прошу делать за меня ТЗ, но не хочу оставлять
позади какую-то неразобранную проблемму.
    

Ответы

Ответ 1

Ваше целое несколько раз завернулось вокруг максимального значения int - 2,147,483,647.

Проверьте:

99923 * 87541 = 8 747 359 343


А также:

На какую цифру должно заканчиваться произведение Ваших двух простых чисел?


Ответ 2

решето работает отлично, ранее искал все простые числа в диапазоне 0- 10 000 000
ушло примерно 15 секунд на планшете. главное правильно написать алгоритм.

возможно я не верно понял ваш алгоритм (прошу исправить меня)

почему второй цикл идет по увеличению параметра, а не от большего к меньшему?

for (j = 3; j <= divNumMax; j++) {



есть нюанс: рассмотрим ту же задачу, но в диапазоне 0-15, пока отбросим условие палиндрома
(здесь оно  не играет роли).

a = 13; b = 2; a*b = 26


но есть и другие простые числа произведение которых даст значительно больше результат?
11*13 > 26


Ответ 3

Вот правильный ответ на задачу, также встречал на собесе:
палиндром - 999949999
множитель1 - 33211
множитель2 - 30109
Реализовал алгоритм так:
Метод поиска наибольшего палиндрома (на входе список простых чисел)

static void palindrome(ArrayList primeNumbers) {
    long palindrome = 0;
    long multiplier1 = 0;
    long multiplier2 = 0;
    for (int j = 0; j < primeNumbers.size(); j++) {
        for (int k = 0; k < primeNumbers.size(); k++) {
            long i = (long) primeNumbers.get(j) * (long) primeNumbers.get(k);
            if (palindromeCheck(i)) {
                if (i > palindrome) {
                    palindrome = i;
                    multiplier1 = primeNumbers.get(j);
                    multiplier2 = primeNumbers.get(k);
                }
            }
        }
    }
    System.out.println("palindrome = " + palindrome
            + "\nmultiplier1 = " + multiplier1
            + "\nmultiplier2 = " + multiplier2);
}  


Метод поиска простых чисел (на входе максимальное и минимальное значения из проверяемого
диапазона чисел):  

static ArrayList eratosthenesPrimeNumbers(int max, int min) {
    ArrayList primeNumbers = new ArrayList<>();
    boolean[] array = new boolean[max];

    for (int i = 2; Math.pow(i, 2) <= max; i++) {
        if (!array[i]) {
            for (int j = (int) Math.pow(i, 2); j < max; j += i) {
                array[j] = true;
            }
        }
    }
    for (int i = max - 1; i >= min; i--) {
        if (!array[i]) {
            primeNumbers.add(i);
        }
    }
    return primeNumbers;
}  


Проверка на то, что найденное число является палиндромом (на входе проверяемое число):  

static boolean palindromeCheck(long i) {
    char[] palindrome = String.valueOf(i).toCharArray();
    int fromBegin = 0;
    int fromEnd = palindrome.length - 1;
    while (fromBegin < fromEnd) {
        if (palindrome[fromBegin] == palindrome[fromEnd]) {
            fromBegin++;
            fromEnd--;
        } else return false;
    }
    return true;
}


Да и еще забыл написать, что эти методы надо вызывать :)
У меня это сделано так:  

public class Main {
static final int MAX_MULTIPLIER = 99999;
static final int MIN_MULTIPLIER = 10000;

public static void main(String[] args) {

    ArrayList primeNumbers2 = new ArrayList<>(eratosthenesPrimeNumbers(MAX_MULTIPLIER,
MIN_MULTIPLIER));
    palindrome(primeNumbers2);
}


и дальше реализация методов...


Ответ 4

Немного вник в алгоритм. По моему, он работает неправильно уже здесь:

 while (isNotPalind) {

            if (sPM <= fPM && sPM > minNum) {
                sPM = findMaxPrimeNumber(sPM - 2);
                isNotPalind = findPalindrome(fPM, sPM);

            } else if (sPM <= minNum) {
                fPM = findMaxPrimeNumber(fPM - 2);
                sPM = fPM;
            }


        }


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

Возьмем отвлеченный от этого пример прогонки от 10 до 1 возможных произведений всех
чисел.

По твоему алгоритму идем по 1-му кругу:

10*10, 10*9 , 10*8, 10*7.... <- и сразу выводим первый попавшийся палиндром

далее второй круг:

9*9, 9*8, 9*7... <- или уж тут сразу выводим первый попавшийся палиндром

далее третий:

8*8, 8*7, 8*6...


И так далее...

Допустим на 1-ом круге 10*2 - это палиндром (гипотетически!)

Также допустим на 2-ом круге 9*8 - это тоже палиндром (гипотетически!)

Но твоя программа выведет 10*2 (несмотря на то что 9*8 больше чем 10*2)

То есть первое попавшееся - это не вариант.
Надеюсь автор меня понял и поправит если я не прав.


Ответ 5

условие задачи подразумевало произведение двух простых пятизначных чисел.
алгоритм работает для двух, трех, четырехзначных чисел. но в упор отказывается работать
для 5-ти. в чем тут ошибка?

public class Palindrome {
    private static final boolean reverse(long value) {
        String str = String.valueOf(value);
        return str.equals(new StringBuilder(str).reverse().toString());
    }

    private static final boolean isPrime(int n) {
        int i;
        for (i = 2; i <= n / 2; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }


    public static void main(String[] args) {

        int i = 0;
        int maxPrimeNumber = 99971;
        int minPrimeNumber = 10007;

        outer:
        for (i = maxPrimeNumber; i >= minPrimeNumber; i--) {
            for (int j = maxPrimeNumber; j >= minPrimeNumber; j--) {

                if (isPrime(i) && isPrime(j)) {
                    long product = j * i;
                    if (reverse(product)) {
                        System.out.printf("%d * %d = %d%n", i, j, product);
                        break outer;
                    }
                }
            }
        }
    }
}

Нахождение всех множителей большого числа в заданном диапазоне

Есть непростое число где-то между 796200000 и 796400000, какой есть наиболее быстрый способ найти все его делители? (в идеале с реализацией) (нужны именно делители, для последующего их использования)
Нет, в гугле меня не забанили, но я не смог быстро разобраться в невероятном разнообразии алгоритмов.
Заранее спасибо.

Ответ

Ну, как мне кажется - найти разложение на простые множители, а затем находить все возможные сочетания простых сомножителей в непростые.
Чтобы найти все простые, достаточно проверить делимость на простые, не большие 28284 (квадратный корень из максимального числа). Чтобы найти все простые - можно заранее то же решето Эратосфена использовать, с проверкой до 168 (очередной квадратный корень).
Что-то типа
vector primus(int max) { vector p { 2 }; vector prime(max+1, true); prime[0] = prime[1] = false; for(int i = 3; i<= max; i += 2) if (prime[i]) { p.push_back(i); if (i*i <= max) for(int j= i*i; j <= max; j+=i) prime[j] = false; } return p; }
int main(int argc, const char * argv[]) { vector p = primus(28300);
int N = 796400000; for(size_t i = 0; i < p.size() && N > p[i]; ++i) { while (N%p[i] == 0) { cout << p[i] << endl; N /= p[i]; } } if (N > 1) cout << N << endl; }
Окончательная полная программа получения всех (не только простых!) делителей всех указанных чисел у меня на машине делает это за 2-3 секунды.