2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 C++ Решето Эратосфена
Сообщение06.07.2012, 17:28 
Здравствуйте! Решил написать программку для поиска простых чисел с помощью Решета Эратосфена. Изучив алгоритм я написал следующий код на С++

код: [ скачать ] [ спрятать ]
Используется синтаксис C++
#include "stdafx.h"
#include <iostream>
#include <new>
#include <locale>

using namespace std;

int main()
{
        setlocale(LC_CTYPE, "russian"); //установка русского языка в консоли

        int i, j; //индексы
        int N; //размер массива
        bool *mas; //объявляем массив типа bool

        cout << "Простые числа от 1 до N \n";
        cout << "Введите число N ";
        cin >> S;
        N=S+1;
        mas= new bool [N]; //динамически выделяем память под массив размером N

        for(i=1; i<=S; i++) mas[i]=true; //заполняем массив значением true;
       
        //Алгоритм "Решето Эратосфена"
        for(i=2; ((i^2)<=S); i++)
                if(mas[i])
                        for(j=(i^2); j<=S; j+=i)
                                if(mas[j]) mas[j]=false;

        //Вывод результата на экран
        for(i=1; i<=S; i++)
                if(mas[i]) cout << i << " ";


        system("pause");
        return 0;
}


Проблема в том, что выдает он какой-то "мусор", вместо простых чисел, да и к тому же почему-то mas[1] после выполнения алгоритма становится равным false.

Код:
Простые числа от 1 до N
Введите число N 100
3 5 9 15 21 33 39 41 45 51 53 59 63 69 75 81 89 93 99


Если поможете разобраться в чем я ошибся буду очень благодарен :-)

 
 
 
 Re: C++ Решето Эратосфена
Сообщение06.07.2012, 17:49 
Цикл по j весьма странный. Вы ведь хотели начальное значение j = i * 2? (Зря, не увидел сразу, что это лишнее. И правда, с квадрата рационально.) К тому же, в C++ нет операции возведения в степень.

 
 
 
 Re: C++ Решето Эратосфена
Сообщение06.07.2012, 17:54 
В C++ нет операции возведения в степень, а ^ это битовый XOR.
Замените i^2 на i*i.

 
 
 
 Re: C++ Решето Эратосфена
Сообщение06.07.2012, 18:58 
venco в сообщении #592804 писал(а):
В C++ нет операции возведения в степень, а ^ это битовый XOR.
Замените i^2 на i*i.


Точно! :) Вот я горе-программист))) Спасибо)

 
 
 
 Re: C++ Решето Эратосфена
Сообщение07.07.2012, 10:20 
Elarium в сообщении #592829 писал(а):
Точно! :) Вот я горе-программист))) Спасибо)

Похоже, это у вас не последняя радость в жизни программиста. Поэтому нужно осваивать средства отладки, радость будет вам ещё большая.

(Оффтоп)

venco,arseniiv
С какой степенью достоверности можно отличить самостоятельное творчество начинающего программиста от "копипастинга"?
 !  Toucan:
hurtsy, оффтопик!


С уважением,

 
 
 [ Сообщений: 5 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group