Найти первое простое число, превосходящее 10^(100) - C++ - Ответ 5357530

@gunslinger · 19.11.2013, 16:22

Нашел кое-что для работы с большими числами: http://netcode.ru/cpp/files/verylong.zip
Может извлекать корень (в некоторых реализациях используется для поиска простого числа) и возводить в степень.

C++

// Verylong.h
 
#ifndef VERYLONG_H
#define VERYLONG_H
 
#include <assert.h>
#include <iostream.h>
#include <iomanip.h>
#include <string.h>
#include <ctype.h>
#include <limits.h>
#include <math.h>
 
class Verylong
{
    private:
//      char *vlstr;
//      int  vlen;
//      int  vlsign;
 
        Verylong multdigit(int) const;
        Verylong mult10(int) const;
 
    public:
 
        char *vlstr;
        int  vlen;
        int  vlsign;
        Verylong(const char* = NULL);
        Verylong(int);
        Verylong(const Verylong &);
        ~Verylong();
 
        operator int() const;
        operator long() const;
        operator double() const;
        operator char * () const;
 
        const Verylong& operator=(const Verylong&);
 
        Verylong operator - () const;
        Verylong operator ++ ();
        Verylong operator ++ (int);
        Verylong operator -- ();
        Verylong operator -- (int);
 
        Verylong operator += (const Verylong &);
        Verylong operator -= (const Verylong &);
        Verylong operator *= (const Verylong &);
        Verylong operator /= (const Verylong &);
        Verylong operator %= (const Verylong &);
 
        friend Verylong operator + (const Verylong &, const Verylong &);
        friend Verylong operator - (const Verylong &, const Verylong &);
        friend Verylong operator * (const Verylong &, const Verylong &);
        friend Verylong operator / (const Verylong &, const Verylong &);
        friend Verylong operator % (const Verylong &, const Verylong &);
 
        friend int operator == (const Verylong &, const Verylong &);
        friend int operator != (const Verylong &, const Verylong &);
        friend int operator < (const Verylong &, const Verylong &);
        friend int operator <= (const Verylong &, const Verylong &);
        friend int operator > (const Verylong &, const Verylong &);
        friend int operator >= (const Verylong &, const Verylong &);
 
        char *strrev(char *s) const;
        friend Verylong abs(const Verylong &);
        friend Verylong sqrt(const Verylong &);
        friend Verylong pow(const Verylong &, const Verylong &);
        friend double div(const Verylong &, const Verylong &);
 
        friend ostream & operator << (ostream &, const Verylong &);
        friend istream & operator >> (istream &, Verylong &);
 
};
 
Verylong zero = Verylong("0");
Verylong one = Verylong("1");
Verylong two = Verylong("2");
 
Verylong::Verylong(const char *value)
{
    if(value)
    {
        vlsign = (*value == '-') ? 1:0;
 
         if(ispunct(*value))
            {
                vlen = strlen(value)-1;
                vlstr = new char[vlen + 1]; assert(vlstr != NULL);
                strcpy(vlstr, value+1);
            }
         else
            {
                vlen = strlen(value);
                vlstr = new char[vlen + 1]; assert(vlstr != NULL);
                strcpy(vlstr, value);
            }
        strrev(vlstr);
    }
    else
        {
            vlstr = new char[2]; assert(vlstr != NULL);
            *vlstr = '0'; *(vlstr+1)= '\0';
            vlen = 1; vlsign = 0;
        }
}
 
Verylong::Verylong(int n)
{
    int i;
    if(n<0) {vlsign = 1; n = (-n); }
    else vlsign = 0;
 
    if (n)
    {
        i = (int)log10(n)+2;
        vlstr = new char[i]; assert(vlstr != NULL);
        vlen = i-1;
        i = 0;
        while (n >= 1)
        {
            vlstr[i] = n%10 + '0';
            n /= 10;
            i++;
        }
        vlstr[i] = '\0';
    }
    else
    {
        vlstr = new char[2]; assert(vlstr != NULL);
        *vlstr = '0'; *(vlstr+1) = '\0';
        vlen = 1;
    }
}
 
Verylong::Verylong(const Verylong& x):vlen(x.vlen),vlsign(x.vlsign)
{
    vlstr = new char[x.vlen + 1]; assert(vlstr != NULL);
    strcpy(vlstr, x.vlstr);
}
 
Verylong::~Verylong() { delete [] vlstr; }
 
Verylong::operator int() const
{
    static Verylong max0(INT_MAX);
    static Verylong min0(INT_MIN+1);
    int number, factor = 1;
    if(*this > max0)
    {
        cerr << "Error: convert Verylong->integer incredible" << endl;
        return INT_MAX;
    }
    else if(*this < min0)
    {
        cerr << "Error: convert Verylong->integer incredible" << endl;
        return INT_MIN;
    }
    number = vlstr[0]-'0';
    for (int j=1; j<vlen; j++)
    {
        factor *= 10;
        number += (vlstr[j]-'0') * factor;
    }
 
    if (vlsign) return -number;
    return number;
}
 
Verylong::operator long() const
{
    static Verylong max0(INT_MAX);
    static Verylong min0(INT_MIN+1);
    long number, factor = 1;
    if(*this > max0)
    {
        cerr << "Error: convert Verylong->integer incredible" << endl;
        return INT_MAX;
    }
    else if(*this < min0)
    {
        cerr << "Error: convert Verylong->integer incredible" << endl;
        return INT_MIN;
    }
    number = vlstr[0]-'0';
    for (long j=1; j<vlen; j++)
    {
        factor *= 10;
        number += (vlstr[j]-'0') * factor;
    }
 
    if (vlsign) return -number;
    return number;
}
 
Verylong::operator double() const
{
    double sum, factor = 1.0;
    sum = double(vlstr[0]-'0');
    for (int i=1; i<vlen; i++)
    {
        factor *= 10.0;
        sum += double(vlstr[i]-'0') * factor;
    }
    return sum;
}
 
Verylong::operator char * () const
{
    char *temp = new char[vlen + 1]; assert(temp != NULL);
    char *s;
 
    if(vlen > 0)
    {
        strcpy(temp, vlstr);
        if (vlsign)
        {
            s = new char[vlen + 2];
            strcpy(s,"-");
        }
        else
        {
            s = new char[vlen + 1];
            strcpy(s,"");
        }
        strcat(s,strrev(temp));
    }
    else
    {
        s = new char[2];
        strcpy(s,"0");
    }
    delete [] temp;
    return s;
}
 
const Verylong & Verylong::operator = (const Verylong &rhs)
{
    if (this == &rhs) return *this;
    delete [] vlstr;
    vlstr = new char [rhs.vlen + 1]; assert(vlstr != NULL);
    strcpy(vlstr, rhs.vlstr);
    vlen = rhs.vlen;
    vlsign = rhs.vlsign;
    return *this;
}
 
Verylong Verylong::operator -() const
{
    Verylong temp(*this);
    if(temp != zero) temp.vlsign = !vlsign;
    return temp;
}
 
Verylong Verylong::operator ++()
{
    return *this = *this + one;
}
 
Verylong Verylong::operator ++ (int)
{
    Verylong result(*this);
 
    *this = *this + one;
    return result;
}
 
Verylong Verylong::operator -- ()
{   return *this = *this - one; }
 
Verylong Verylong::operator -- (int)
{
    Verylong result(*this);
    *this = *this - one;
    return result;
}
 
Verylong Verylong::operator += (const Verylong& v)
{   return *this = *this + v; }
 
Verylong Verylong::operator -= (const Verylong& v)
{   return *this = *this - v; }
 
Verylong Verylong::operator *= (const Verylong& v)
{   return *this = *this * v; }
 
Verylong Verylong::operator /= (const Verylong& v)
{   return *this = *this / v; }
 
Verylong Verylong::operator %= (const Verylong& v)
{   return *this = *this % v; }
 
Verylong operator + (const Verylong &u, const Verylong &v)
{
    if (u.vlsign ^ v.vlsign)
    {
        if (u.vlsign == 0) { Verylong t1 = u-abs(v); return t1; }
        else               { Verylong t2 = v-abs(u); return t2; }
    }
 
    int j, d1, d2, digitsum, carry = 0,
        maxlen = (u.vlen > v.vlen) ? u.vlen:v.vlen;
    char *temp = new char[maxlen + 2]; assert (temp != NULL);
 
    for (j=0; j<maxlen; j++)
    {
        d1 = (j > u.vlen - 1) ? 0 : u.vlstr[j] - '0';
        d2 = (j > v.vlen - 1) ? 0 : v.vlstr[j] - '0';
        digitsum = d1 + d2 + carry;
        if (digitsum >= 10)
        {
            digitsum -= 10;
            carry = 1;
        }
        else
        carry = 0;
        temp[j] = digitsum + '0';
    }
 
    if (carry)
        temp[j++] = '1';
 
    if (u.vlsign) temp [j++] = '-';
 
    temp[j] = '\0';
    u.strrev(temp);
    Verylong result(temp);
    delete [] temp;
    return result;
}
 
Verylong operator - (const Verylong &u, const Verylong &v)
{
    if (u.vlsign ^ v.vlsign)
    {
        if(u.vlsign == 0) { Verylong t1 = u + abs(v); return t1; }
        else              { Verylong t2 = -(v + abs(u)); return t2;}
    }
 
    int maxlen = (u.vlen > v.vlen) ? u.vlen:v.vlen,
        d, d1, d2, i, negative, borrow = 0;
    char *temp = new char[maxlen + 1]; assert(temp != NULL);
 
    Verylong w,y;
 
    if (u.vlsign == 0)
        if (u < v)  { w = v; y = u; negative = 1; }
        else        { w = u; y = v; negative = 0; }
    else
        if (u < v)  { w = u; y = v; negative = 1; }
        else        { w = v; y = u; negative = 0; }
 
    for (i=0; i<maxlen; i++)
    {
        d1 = (i > w.vlen - 1) ? 0 : w.vlstr[i] - '0';
        d2 = (i > y.vlen - 1) ? 0 : y.vlstr[i] - '0';
        d = d1 - d2 - borrow;
        if (d < 0)
        {
            d += 10;
            borrow = 1;
        }
        else
            borrow = 0;
        temp[i] = d + '0';
    }
 
    while (i - 1 > 0 && temp[i - 1] == '0')
        --i;
 
    if (negative)   temp[i++] = '-';
    temp[i] = '\0';
    u.strrev(temp);
 
    Verylong result(temp);
    delete [] temp;
    return result;
}
 
Verylong operator * (const Verylong &u, const Verylong &v)
{
    Verylong pprod("1"), tempsum("0");
 
    for (int j=0; j<v.vlen; j++)
    {
        int digit = v.vlstr[j] - '0';
        pprod = u.multdigit(digit);
        pprod = pprod.mult10(j);
 
        tempsum += pprod;
    }
 
    tempsum.vlsign = u.vlsign ^ v.vlsign;
    return tempsum;
}
 
Verylong operator / (const Verylong &u, const Verylong &v)
{
    Verylong w, y, b, c, d, quotient = Verylong("0");
    int len = u.vlen - v.vlen;
    if (v == Verylong("0"))
    {
        cerr << "Error: divide by zero" << endl;
        return Verylong("0");
    }
    w = abs(u); y = abs(v);
    if (w < y) return Verylong("0");
 
    char *temp = new char[w.vlen+1]; assert(temp != NULL);
    strcpy(temp, w.vlstr + len);
    b.strrev(temp);
    c = Verylong(temp);
    delete [] temp;
    for (int i=0; i<=len; i++)
    {
        quotient = quotient.mult10(1);
        b = d = Verylong("0");
        while (b < c)
            {   b = b + y; d = d + Verylong("1"); }
        if (c < b)
        {
            b = b - y;
            d = d - Verylong("1");
        }
 
        quotient = quotient + d;
 
        if (i < len)
        {
            c = (c-b).mult10(1);
            c = c + Verylong(w.vlstr[len-i-1]-'0');
        }
    }
 
    quotient.vlsign = u.vlsign^v.vlsign;
    return quotient;
}
 
Verylong operator % (const Verylong &u, const Verylong &v)
{
    return (u - v * (u / v));
}
 
int operator == (const Verylong &u, const Verylong &v)
{
    return (u.vlsign == v.vlsign && !strcmp(u.vlstr, v.vlstr));
}
 
int operator != (const Verylong &u, const Verylong &v)
{
    return !(u==v);
}
 
int operator < (const Verylong &u, const Verylong &v)
{
    if      (u.vlsign < v.vlsign) return 0;
    else if (u.vlsign > v.vlsign) return 1;
    if      (u.vlen < v.vlen) return (1^u.vlsign);
    else if (u.vlen > v.vlen) return (0^u.vlsign);
 
    int temp;
    char *temp1 = new char[u.vlen + 1], *temp2 = new char[v.vlen + 1];
    assert(temp1 != NULL);
    assert(temp2 != NULL);
 
    strcpy(temp1, u.vlstr);
    strcpy(temp2, v.vlstr);
    u.strrev(temp1);
    u.strrev(temp2);
 
    temp = strcmp(temp1, temp2);
    delete [] temp1; delete [] temp2;
 
    if (temp < 0)
        return (1^u.vlsign);
    else if (temp > 0)
        return (0^u.vlsign);
    else
        return 0;
}
 
int operator <= (const Verylong &u, const Verylong &v)
{
    return (u < v || u == v);
}
 
int operator > (const Verylong &u, const Verylong &v)
{
    return (!(u<v) && u!=v);
}
 
int operator >= (const Verylong &u, const Verylong &v)
{
    return (u>v || u==v);
}
 
Verylong abs(const Verylong &v)
{
    Verylong u(v);
    if (u.vlsign) u.vlsign = 0;
    return u;
}
 
Verylong sqrt(const Verylong &v)
{
    if (v.vlsign) {cerr << "NaN" << endl; return zero;}
 
    int j, k = v.vlen + 1, num = k >> 1;
    Verylong y, z, sum, tempsum, digitsum;
 
    char *temp = new char[num + 1]; assert(temp != NULL);
    char *w = new char[k];          assert(w != NULL);
 
    strcpy(w, v.vlstr);
    k = v.vlen - 1;
    j = 1;
    if (v.vlen % 2) digitsum = Verylong(w[k--] - '0');
    else
    {
        digitsum = Verylong((w[k] - '0')*10 + w[k-1] - '0');
        k -= 2;
    }
 
    sum = z = Verylong(int(sqrt(double(digitsum))));
 
    temp[0] = int(z) + '0';
    digitsum -= z*z;
 
    for(; j<num; j++)
    {
        digitsum = digitsum.mult10(1) + Verylong(w[k--] - '0');
        y = z+z;
        z = digitsum/y;
        tempsum = digitsum.mult10(1) + Verylong(w[k] - '0');
        digitsum = -y*z.mult10(1) + tempsum - z*z;
 
        while (digitsum < zero)
        {
            --z;
            digitsum = -y*z.mult10(1) + z;
        }
        --k;
 
        temp[j] = int(z) + '0';
        z = sum = sum.mult10(1) + z;
    }
 
    temp[num] = '\0';
    Verylong result(temp);
    delete [] temp; delete [] w;
    return result;
}
 
Verylong pow(const Verylong &X, const Verylong degree)
{
    Verylong N(degree), Y("1"), x(X);
    if(N == Verylong("0")) return Verylong("1");
    if(N < Verylong("0")) return Verylong("0");
 
    while(1)
    {
        if (N%Verylong("2") != Verylong("0"))
        {
            Y = Y * x;
            N = N / Verylong("2");
            if (N == Verylong("0")) return Y;
        }
        else N = N / Verylong("2");
        x = x * x;
    }
}
 
double div(const Verylong &u, const Verylong &v)
{
    double qq=0.0, qqscale = 1.0;
    Verylong w, y, b, c;
    int d, count, decno = 16;
 
    if (v == Verylong("0"))
    {
        cerr << "ERROR: Divide by zero" << endl;
        return 0.0;
    }
    if (u == Verylong("0")) return 0.0;
 
    w=abs(u); y=abs(v);
    while(w<y) { w = w.mult10(1); qqscale *= 0.1; }
 
    int len = w.vlen - y.vlen;
    char *temp = new char[w.vlen + 1]; assert(temp != NULL);
 
    strcpy(temp, w.vlstr + len);
    w.strrev(temp);
    c = Verylong(temp);
    delete [] temp;
 
    for (int i=0; i<=len; i++)
    {
        qq *= 10.0;
        b = Verylong("0"); d = 0;
 
        while (b < c)
        { b += y; d += 1; }
 
        if (c < b)
        { b -= y; d -= 1; }
 
        qq += double(d);
        c = (c-b).mult10(1);
 
        if (i < len)
            c += Verylong(w.vlstr[len - i - 1] - '0');
    }
 
    qq *= qqscale; count = 0;
 
    while (c != Verylong("0") && count < decno)
    {
        qqscale *= 0.1;
 
        b = Verylong("0"); d = 0;
 
        while (b < c)
        { b += y; d += 1; }
 
        if (c < b)
        { b -= y; d -= 1; }
 
        qq += double(d)*qqscale;
 
        c = (c-b).mult10(1);
        count++;
    }
    if (u.vlsign^v.vlsign) qq *= (-1.0);
    return qq;
}
 
ostream & operator << (ostream &s, const Verylong &v)
{
    char *temp = new char[v.vlen + 1]; assert(temp != NULL);
    if (v.vlen > 0)
    {
        strcpy(temp, v.vlstr);
        if (v.vlsign) s << "-";
        s << v.strrev(temp);
    }
    else s << "0";
    delete [] temp;
    return s;
}
 
istream & operator >> (istream &s, Verylong &v)
{
    char* temp;
    s >> temp;
 
    delete [] v.vlstr;
    v.vlen = strlen(temp);
    v.strrev(temp);
    v.vlstr = new char[v.vlen + 1]; assert(v.vlstr != NULL);
    strcpy(v.vlstr, temp);
    return s;
}
 
 
char * Verylong::strrev(char *s) const
{
    int len = strlen(s), len1 = len - 1, index,
        limit = len >> 1;
    char t;
 
    for (int i=0; i<limit; i++)
    {
        index = len1-i;
        t = s[index];
        s[index] = s[i];
        s[i] = t;
    }
    return s;
}
 
Verylong Verylong::multdigit(int num) const
{
    int j, carry = 0;
    if (num)
    {
        char *temp = new char[vlen + 2]; assert(temp != NULL);
        for(int j = 0; j<vlen; j++)
        {
            int d1 = vlstr[j] - '0',    digitprod = d1*num + carry;
 
            if (digitprod >= 10)
            {
                carry = digitprod/10;
                digitprod -= carry*10;
            }
            else carry = 0;
            temp[j] = digitprod + '0';
        }
 
        if (carry)
            temp[j++] = carry + '0';
        temp[j] = '\0';
 
        strrev(temp);
        Verylong result(temp);
        delete [] temp;
        return result;
    }
    else return zero;
}
 
Verylong Verylong::mult10(int num) const
{
    if (*this != zero)
    {
        int j, dd = vlen + num, bb = vlen - 1;
        char *temp = new char [dd + 1]; assert(temp != NULL);
 
        for (j=0; j<vlen; j++)  temp[j] = vlstr[bb-j];
        for (j=vlen; j<dd; j++) temp[j] = '0';
 
        temp[dd] = '\0';
        Verylong result(temp);
        delete [] temp;
        return result;
    }
    else return zero;
}
#endif

P.S.: в работе не проверял.

Вернуться к обсуждению:
Найти первое простое число, превосходящее 10^(100) C++

Следующий ответ

Другие темы раздела
C++ инициализация указателя https://www.cyberforum.ru/ cpp-beginners/ thread1011083.html class Item { public: Item() { num0=new char("как");//ошибка cannot convert from 'const char ' to 'char' num1=new char("это");//ошибка cannot convert from 'const char ' to 'char' num2=new char("исправить");//ошибка cannot convert from 'const char ' to 'char' } char* num0;	C++ Машина Поста (да пофиг) #include <iostream> #include <fstream> #include <istream> #include <stdlib.h> #include <string> using namespace std; struct rule{ string Left;
C++ Найти корни квадратного уравнения https://www.cyberforum.ru/ cpp-beginners/ thread1011079.html Помогите решить. Найти корни квадратного уравнения y=ax2+bx+c, b– вводится с клавиатуры, a=3b-3, c=a-3b.	C++ перевести на двумерный массив 1. #include <iostream> using namespace std; int main(){ int n;cout<<"n=";cin>>n; int a; for (int i=0;i<n;++i) {cout<<"a="; cin>>a; if (a<0)a=5;} for (int i=0; i<3;++i)cout<<a<<endl; system ("pause"); https://www.cyberforum.ru/ cpp-beginners/ thread1011076.html
Инкремент указателей и как обратиться к "промежуточному" адресу переменной C++ Доброго времени суток! Пусть указатель указывает на адрес переменной типа int. Переменная типа int занимает 4 байта (пускай она находится по адресу 0x100). Тогда указатель указывает на адрес 0x100. Почему инкрементируя адрес в указателе на 1, указатель указывает на адрес 0x104, а не на 0x101? И что получится, если обратиться к адресу 0x101? Наверное, вопрос глупый. Прошу прощения	C++ Массивы https://www.cyberforum.ru/ cpp-beginners/ thread1011051.html Пусть t0=1, tk= t0+ tk-2+…+ tk-10, k=1,2,… Получить t10
C++ Объединение и упорядочивание двух множеств Пожалуйста помогите исправить код программы, он в некоторых случаях работает не верно. Очень срочно!!! Пусть заданы два множества А и В в виде неупорядоченных числовых последовательностей. Создать программу, которая упорядочивает существующие множества и определяет объединения двух множеств порядка 7 и 12. Код программы #include <iostream> #include <string> #include <fstream> using... https://www.cyberforum.ru/ cpp-beginners/ thread1011012.html	C++ Получение объекта из множества Здравствуйте! У меня есть класс с множеством class AutoShop { string name; string address; int amountCarsSold; double gainsMoney; set<Manager> managerSet; set<Client> clientSet;
C++ Разработать программу предназнченную для зашифровки текстов https://www.cyberforum.ru/ cpp-beginners/ thread1010997.html Разработать программу предназнченную для зашифровки текстов. Вывести на экран исходный текст и результат шифровки. Добавлено через 3 минуты И еще.... исходный текст и результат шифрования должны храниться в файлах... Плииизз!!!	C++ Запутался в циклах https://www.cyberforum.ru/ cpp-beginners/ thread1010995.html Вроде бы все сделал правильно но есть ошибка Заполняю массив рандомными числами потом скалдываю все числа массива и записую результат в одтельный массив и вывожу в мемо все нормально но есть 3 огромных числа которых не должно быть вот код 1ая {int i; for (i=0; i < 9; i++) { a=rand()%30-10; Memo1->Lines->Add(a); } }
Задача на сортировку массивов C++ Сформировать с помощью датчика случайных чисел в диапазоне два массива C и D, из 20 элементов целого типа каждый. Вывести их на экран. Отсортировать массивы C и D по возрастанию и сформировать из них массив E, таким образом, чтобы он также был отсортирован. Суть такова, что я понял как сортировать 2 массива - сравнивать C и D и тот, который меньше, заносить в E, но не могу сообразить что...	C++ сумма соответствующих элементов массивов https://www.cyberforum.ru/ cpp-beginners/ thread1010987.html даны два массива из n элементов, создать третий массив, из суммы соответствующих элементов первых 2х массивов. Использовать функцию. Элементы массива вводить с клавиатуры. Помогите!

	19.11.2013, 16:22