0

エラトステネス アルゴリズムを実装して素数を計算し、順序付けされた方法で入力するこの単純なコードを作成しました。問題は、1020 より大きい数値では機能しないことです。誰かがこの理由を教えてもらえますか? 実行すると、Eclipse は exe ファイルを起動できず、数値の計算を停止します。ただし、Java で記述された同じコードは、10 億未満の数値でもうまく機能します。

#include <iostream>
#include<math.h>
using namespace std;


int main() {
    int N;
    cin >> N;
    int* a = new int[N];

    int i , j, k, cnt = 0;
        for(a[1] = 0, i = 2; i <= N; i++) a[i] = 1;
    for(i = 2; i <= N/2; i++)
        for(j = 2; j <= N/i; j++)
            a[i*j] = 0;


        for(i = 1; i <= N; i++)
            if(a[i]) {
                cout<< i ;
                int lengthi = (int)floor(log10((float)i));
                int lengthN = (int)floor(log10((float)N)) + 1;
                    for(k = 0; k < lengthN - lengthi + 1; k++)
                         cout<<' ';
                cnt++;
                if(cnt%10==0) cout<<'\n';
            }

    delete [] a;
    return 0;
}
4

1 に答える 1

3

あなたのフォーマットは恐ろしいですがstd::vector、ループを手動で管理する代わりに使用するように変換した後は、正常に動作します:

http://ideone.com/y2CML7

#include <cmath>
#include <iostream>
#include <vector>

int main() 
{
    int N = 1020;

    std::vector<int> a;
    a.resize(N);

    int i, j, k, cnt = 0;
    a[0] = 0;
    for(i = 1; i < N; i++) // fixed your indexing here
    {   
        a[i] = 1;
    }

    for(i = 2; i <= N/2; i++)
    {
        for(j = 2; j <= N/i; j++)
        {
            a[i*j] = 0; // I haven't done the math, but this may go out of bounds as well
        }
    }


    for(i = 1; i <= N; i++)
    {
        if(a[i]) 
        {
            std::cout << i;
            int lengthi = (int)std::floor(std::log10((float)i));
            int lengthN = (int)std::floor(std::log10((float)N)) + 1;
            for(k = 0; k < lengthN - lengthi + 1; k++)
            {
                std::cout << ' ';
            }
            cnt++;

            if(cnt%10==0)
            {
                std::cout << '\n';
            }
        }
    }

    return 0;
}

またはアルゴリズムの単純化されたバージョン:

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>


struct moduloFunctor
{
    int mod;

    moduloFunctor(int m) : mod(m) {}

    bool operator()(int i)
    {
        return (i % mod == 0 && i != mod);
    }
};


int main()
{
    std::vector<int> numbers;
    int maximum = 1020;
    //std::cin >> maximum;
    numbers.reserve(maximum - 1); // starting at 2
    for (int i = 2; i <= maximum; ++i)
    {
        numbers.push_back(i);
    }

    int cnt = 0;
    do
    {
        moduloFunctor func(numbers[cnt++]);
        numbers.erase(std::remove_if(numbers.begin(), numbers.end(), func), numbers.end()); 
    } while (cnt < numbers.size());

    std::cout << "Primes:  " << std::endl;
    std::copy(numbers.begin(), numbers.end(), std::ostream_iterator<int>(std::cout, " "));

    return 0;
}
于 2013-09-13T18:40:11.813 に答える