Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Для новичков > помогите переделать С++ в СИ

Автор: Splendid 18.8.2008, 11:21

Нужно переделать этот код в Си, помогите, пожалуйста...

Код



#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <vector>

template <class T, class T2>
const std::vector<T> & get_primes (const T & b, T2 & pi)
{

    static std::vector<T> primes;
    static T counted_b;

    
    if (counted_b >= b)
        pi = T2 (std::upper_bound (primes.begin(), primes.end(), b) - primes.begin());
    else
    {
    

        if (counted_b == 0)
        {
            primes.push_back (2);
            counted_b = 2;
        }

       
        T first = counted_b == 2 ? 3 : primes.back()+2;
        for (T cur=first; cur<=b; ++++cur)
        {
            bool cur_is_prime = true;
            for (std::vector<T>::const_iterator iter = primes.begin(), end = primes.end();
                iter != end; ++iter)
            {
                const T & div = *iter;
                if (div * div > cur)
                    break;
                if (cur % div == 0)
                {
                    cur_is_prime = false;
                    break;
                }
            }
            if (cur_is_prime)
                primes.push_back (cur);
        }
        
        counted_b = b;
        pi = (T2) primes.size();

    }
    
    return primes;

}


template <class T, class T2>
T2 prime_div_trivial (const T & n, T2 m)
{
    
   
    if (n == 2 || n == 3)
        return 1;
    if (n < 2)
        return 0;
    if (even (n))
        return 2;


    T2 pi;
    const vector<T2> & primes = get_primes (m, pi);
 
    for (std::vector<T2>::const_iterator iter=primes.begin(), end=primes.end();
        iter!=end && *iter <= m; ++iter)
    {
        const T2 & div = *iter;
        if (div * div > n)
            break;
        else
            if (n % div == 0)
                return div;
    }
    
    if (n < m*m)
        return 1;
    return 0;

}

Автор: W4FhLF 18.8.2008, 11:30

Для этого кода невозможно получить полноценный аналог на С, т.к. в нём нет шаблонов и понятия обобщённого программирования (вариант с кучей макросов не рассматриваю).

В коде активно используются контейнеры, алгоритмы и итераторы STL. Их можно заменить реализовав всё вручную.

Поэтому я очень сомневаюсь, что здесь кто-то будет переделывать за тебя всё это. Задавай более конкретные вопросы.

Автор: Splendid 20.8.2008, 11:38

вот более конкретный вопрос:

Как полученные этим кодом:

Код



#include <stdio.h>
#define N 256
//алгоритм "решето Эвклида"

int main(){

    unsigned int a[256];
    int i, s, j;
   //заполним все ячейки числами по порядку: 0,1,2,3...
   for( i=0; i<N; i++){
       a[i] = i;
   }
   //поскольку 1 не простое число, обнулим ячейку с этим числом
   a[1]=0;
   
   for (s=2; s<N; s++){
       if(a[s]!=0){
       for(j=s*2; j<N; j+=s){
           a[j]=0;
       }
       }
   }
   for(i=0; i<N; i++){
       if(a[i]!=0){
       printf("%d\n", a[i]);
       }
   }

}

простые числа - т.е. последовательость a[i], передать в цикл....

Пробую так дописать - фигня получается:

Код


Код:

   for(i=0; i<N; i++){
       if(a[i]!=0 && n % a[i]==0){
       return 0;
       }
       return 1;
   }
  
       
}

main() 

{
      int n=0;
        printf( "Enter any number -> \n");
        scanf("%u", &n);
        printf("%s\n",
            (
                delimost (n) ?
                "It is possibly a prime number" :
                "It is composite number"
            )
        );
    return 0;

}

а нужно, чтобы цикл брал все ненулевые a[i] (т.е. все простые числа) по порядку и делил n на каждое из них, и если все остатки не равны нулю - то выводил бы - It is possibly a prime number

Автор: NoliX 20.8.2008, 12:58

Я так понимаю, что требуется проверить, является ли число простым
В данном случае написан код - решето Эратосфена для первых 256 чисел

Если требуется проверить, является ли число, N<256 простым то достаточно ввести проверку

Код


if (a[N] == 0) 
   printf ("It is possibly a prime number");

Потому что по алгоритму мы вычеркивали все составные числа из нашего массива

Если требуется проверить, является ли число, 256<N<66049 (это 257*257) простым то придется действительно делить но все простые числа меньше 256
для нужно исправить

Код


for(i=0; i<N; i++){
       if(a[i]!=0 && n % a[i]==0){
       return 0;
       }
       return 1;
   }

на

Код


for (i=0; ((i<(n/2 + 1)) && (i<N)); i++){
       if((a[i]!=0) && (n % a[i]==0)){
       return 0;
       }
   }
return 1;

хотя вместо i<(n/2) правильно писать i<sqrt(n) (квадратный корень)

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

логичнее в этом случае я думаю сделать так

Код


#include "stdafx.h"

bool isPrime (unsigned int n){
    for (unsigned int i=2; i<(n/2+1);i++){
        if (n % i == 0) 
            return false;
    }
    return true;
}

int _tmain(int argc, _TCHAR* argv[]){
    unsigned int n=0;
    printf( "Enter any number -> \n");
    scanf("%u", &n);

    if (isPrime(n)) 
        printf("It is possibly a prime number\n");
    else
        printf("It is composite number\n");

    return 0;
}

Автор: Splendid 20.8.2008, 13:18

в алгоритме нужно заданное число методом тривиального деления проверить на простоту, для этого решетом Эратосфена вычисляются все простые числа до 256 - я так понимаю, что это оптимальная проверка, отсекает все четные и 80% нечетных составных чисел, а потом заданное число поделить на все эти полученные простые....я переписала этот цикл так:

Код


 for(i=0; i<N; i++){

        if(a[i]!=0 && a[i]!=n && n % a[i]==0)
        
        {
            //printf("%d\n", a[i]);
            return 0;
        }

вроде работает....это правильно?

Автор: NoliX 20.8.2008, 14:01

Вы меня не читаете (слушаете)

я уже написал, что нужно написать вот так:

Код


for (i=0; ((i<(n/2 + 1)) && (i<N)); i++){
       if((a[i]!=0) && (n % a[i]==0)){
       return 0;
       }
   }
return 1;

В Вашем коде Вам, может быть, придется делить на заведомо большие проверяемого числа числа, например не нужно делить 5 на 33, и так понятно, что 5 больше чем на 3 не поделится (а это 5/2+1)

А по поводу, что не гарантирует правильности результата - это я конечно чушь спорол, ошибка будет только после 66049

Автор: Splendid 20.8.2008, 15:02

NoliX, спасибо! Я все поняла!!! Тему можно закрыть smile

Автор: virtul 2.9.2008, 10:47

Модератор: Сообщение скрыто.