Algoritm: Eratosthenning o'chog'idan foydalanib, barcha asosiy raqamlarni yozing

I have implemented Sieve of Eratosthenes for finding the list of prime number from 1 to n. My code is working fine for inputs from 1 to 10,000 but I am getting following for values >100,000:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -2146737495
        at SieveOfEratosthenes.main(SieveOfEratosthenes.java:53)

i * i funktsiyasini amalga oshirganingizda, intervalli ( Integer.MAX_VALUE Men yechimni topa olmadim. Kimdir menga qanday o'zgarishlarni taklif qilishi mumkin va kimdir menga ushbu dasturda samaradorlik uchun biron bir yaxshilanishni taklif qilsa, buni qadrlayapmanmi?

public class SieveOfEratosthenes {

    public static void main(String[] args) {

        Integer num = Integer.parseInt(args[0]);
        Node[] nodes = new Node[num + 1];

        for(int i = 1; i < nodes.length; i++) {

            Node n = new Node();
            n.setValue(i);
            n.setMarker(true);

            nodes[i] = n;
        }

        for(int i = 1; i < nodes.length; i++) {

            if(nodes[i].getMarker() && nodes[i].getValue() > 1) {
                System.out.println("Prime " + nodes[i].getValue());
            } else {
                continue;
            }

            for(int j = i * i; j < nodes.length
                                    && nodes[i].getMarker(); j = j + i) {
                nodes[j].setMarker(false);
            }
        }

        System.out.println(l.size());

    }
}

class Node {

    private int value;
    private boolean marker;

    public void setValue(int value) {
        this.value = value;
    }

    public int getValue() {
        return this.value;
    }

    public void setMarker(boolean marker) {
        this.marker = marker;
    }

    public boolean getMarker() {
        return this.marker;
    }

    public String toString() {
        return ("Value : " + marker + " value " + value);
    }
}
1
Bundan tashqari, Math.abs (j) ni sinab ko'rdim va u ba'zi bir yaxshilanishlarni ko'rsatdi, biroq boshqa muammolar ham xuddi shunday.
qo'shib qo'ydi muallif Vishrant, manba
@ScaryWombat Men buni allaqachon sinab ko'rdim, va men array uzoq qiymatdan foydalanib bo'lmaydi. uning Java docs da
qo'shib qo'ydi muallif Vishrant, manba
@ScaryWombat Men buni allaqachon sinab ko'rdim, va men array uzoq qiymatdan foydalanib bo'lmaydi. uning Java docs da
qo'shib qo'ydi muallif Vishrant, manba
qo'shib qo'ydi muallif Vishrant, manba
qo'shib qo'ydi muallif Vishrant, manba
Aloqa uchun tashakkur. @ScaryWombat
qo'shib qo'ydi muallif Vishrant, manba
Aloqa uchun tashakkur. @ScaryWombat
qo'shib qo'ydi muallif Vishrant, manba
@DavidChoweller biz sizning kodingizni j> 0 deb atashimiz mumkin, ammo hali ham muammo bir xil emasmi? Men 100 mingdan ortiq natijaga erisha olmayman
qo'shib qo'ydi muallif Vishrant, manba
@DavidChoweller biz sizning kodingizni j> 0 deb atashimiz mumkin, ammo hali ham muammo bir xil emasmi? Men 100 mingdan ortiq natijaga erisha olmayman
qo'shib qo'ydi muallif Vishrant, manba
Bundan tashqari, Math.abs (j) ni sinab ko'rdim va u ba'zi bir yaxshilanishlarni ko'rsatdi, biroq boshqa muammolar ham xuddi shunday.
qo'shib qo'ydi muallif Vishrant, manba
@DavidChoweller i * i Integer.MAX_VALUE dan ortda qolayotganini va Java ning ikkita komplektni -2146737495 qiymatidan foydalanganligini aytib o'tganimdek, katalogdan katalogdan topilgan qatorni topish uchun va uning 100,000 emas 10,000 ikkita zeros;)
qo'shib qo'ydi muallif Vishrant, manba
@DavidChoweller i * i Integer.MAX_VALUE dan ortda qolayotganini va Java ning ikkita komplektni -2146737495 qiymatidan foydalanganligini aytib o'tganimdek, katalogdan katalogdan topilgan qatorni topish uchun va uning 100,000 emas 10,000 ikkita zeros;)
qo'shib qo'ydi muallif Vishrant, manba
@DavidChoweller 100000
qo'shib qo'ydi muallif Scary Wombat, manba
@DavidChoweller 100000
qo'shib qo'ydi muallif Scary Wombat, manba
Nimaga 10 mingdan ortiq raqamlar uchun ishlamayotganini tushuntirmaslik.
qo'shib qo'ydi muallif David Choweller, manba
Nimaga 10 mingdan ortiq raqamlar uchun ishlamayotganini tushuntirmaslik.
qo'shib qo'ydi muallif David Choweller, manba
Java'dagi qator ko'rsatkichlari int ma`lumotlaridir, men tushunganimdek, qator qator joylar soni 2 milliardga yaqin.
qo'shib qo'ydi muallif David Choweller, manba
Java'dagi qator ko'rsatkichlari int ma`lumotlaridir, men tushunganimdek, qator qator joylar soni 2 milliardga yaqin.
qo'shib qo'ydi muallif David Choweller, manba
@Vishrant Men taklif qilmadim j> 0 . Men bilgan Eratosthenes algoritmidan siltab, 100 ming raqamga osongina ishlaydi. Birinchidan, barcha raqamlarni ajratadi. So'ngra, n ning kvadrat ildizidan uchga boradi, har safar 2-qo'shiladi va ularning har biri uchun bu sonning barcha kattaliklarini kesib o'tadi.
qo'shib qo'ydi muallif David Choweller, manba
@Vishrant Men taklif qilmadim j> 0 . Men bilgan Eratosthenes algoritmidan siltab, 100 ming raqamga osongina ishlaydi. Birinchidan, barcha raqamlarni ajratadi. So'ngra, n ning kvadrat ildizidan uchga boradi, har safar 2-qo'shiladi va ularning har biri uchun bu sonning barcha kattaliklarini kesib o'tadi.
qo'shib qo'ydi muallif David Choweller, manba
@Vishrant Men taklif qilmadim j> 0 . Men bilgan Eratosthenes algoritmidan siltab, 100 ming raqamga osongina ishlaydi. Birinchidan, barcha raqamlarni ajratadi. So'ngra, n ning kvadrat ildizidan uchga boradi, har safar 2-qo'shiladi va ularning har biri uchun bu sonning barcha kattaliklarini kesib o'tadi.
qo'shib qo'ydi muallif David Choweller, manba

6 javoblar

Aslida for (int j = i * i; ... pastadir i ning barcha koeffitsiyentlarini kesib o'tishdir. Barcha kichikroq kichkina kichik kichik bo'linishlar allaqachon kesib tashlanganligi sababli, faqat i * i dan boshlash uchun mantiqan to'g'ri keladi.

Bu erdan borishning kamida ikkita usuli bor.

Birinchidan i * i o'rniga i * 2 dan o'tishni boshlashingiz mumkin. Bu toshqindan xalos bo'ladi. Yomon tomonda, avvalgi murakkabligi O (n log log n) dan O (n log n) ga qadar o'sadi.

Second, you can check whether i * i is already too much, and if it is, skip the loop completely. Recall that it is essentially skipped anyway for i greater than the square root of nodes.length if no overflow occurs. For example, just add an if (i * 1L * i < nodes.length) before the loop.

3
qo'shib qo'ydi

Aslida for (int j = i * i; ... pastadir i ning barcha koeffitsiyentlarini kesib o'tishdir. Barcha kichikroq kichkina kichik kichik bo'linishlar allaqachon kesib tashlanganligi sababli, faqat i * i dan boshlash uchun mantiqan to'g'ri keladi.

Bu erdan borishning kamida ikkita usuli bor.

Birinchidan i * i o'rniga i * 2 dan o'tishni boshlashingiz mumkin. Bu toshqindan xalos bo'ladi. Yomon tomonda, avvalgi murakkabligi O (n log log n) dan O (n log n) ga qadar o'sadi.

Second, you can check whether i * i is already too much, and if it is, skip the loop completely. Recall that it is essentially skipped anyway for i greater than the square root of nodes.length if no overflow occurs. For example, just add an if (i * 1L * i < nodes.length) before the loop.

3
qo'shib qo'ydi

Aslida for (int j = i * i; ... pastadir i ning barcha koeffitsiyentlarini kesib o'tishdir. Barcha kichikroq kichkina kichik kichik bo'linishlar allaqachon kesib tashlanganligi sababli, faqat i * i dan boshlash uchun mantiqan to'g'ri keladi.

Bu erdan borishning kamida ikkita usuli bor.

Birinchidan i * i o'rniga i * 2 dan o'tishni boshlashingiz mumkin. Bu toshqindan xalos bo'ladi. Yomon tomonda, avvalgi murakkabligi O (n log log n) dan O (n log n) ga qadar o'sadi.

Second, you can check whether i * i is already too much, and if it is, skip the loop completely. Recall that it is essentially skipped anyway for i greater than the square root of nodes.length if no overflow occurs. For example, just add an if (i * 1L * i < nodes.length) before the loop.

3
qo'shib qo'ydi
    for(int i = 1; i < nodes.length; i++) {
        if(nodes[i].getMarker() && nodes[i].getValue() > 1) {
            System.out.println("Prime " + nodes[i].getValue());
        } else {
            continue;
        }

TO

int limit = 2 << 14;
for(int i = 1; i < nodes.length; i++) {
    if(nodes[i].getMarker() && nodes[i].getValue() > 1 && i <= 2 << 15) {
        System.out.println("Prime " + nodes[i].getValue());
        if (i > limit) {
            continue;
        }
    } else {
        continue;
    }
0
qo'shib qo'ydi
    for(int i = 1; i < nodes.length; i++) {
        if(nodes[i].getMarker() && nodes[i].getValue() > 1) {
            System.out.println("Prime " + nodes[i].getValue());
        } else {
            continue;
        }

TO

int limit = 2 << 14;
for(int i = 1; i < nodes.length; i++) {
    if(nodes[i].getMarker() && nodes[i].getValue() > 1 && i <= 2 << 15) {
        System.out.println("Prime " + nodes[i].getValue());
        if (i > limit) {
            continue;
        }
    } else {
        continue;
    }
0
qo'shib qo'ydi
    for(int i = 1; i < nodes.length; i++) {
        if(nodes[i].getMarker() && nodes[i].getValue() > 1) {
            System.out.println("Prime " + nodes[i].getValue());
        } else {
            continue;
        }

TO

int limit = 2 << 14;
for(int i = 1; i < nodes.length; i++) {
    if(nodes[i].getMarker() && nodes[i].getValue() > 1 && i <= 2 << 15) {
        System.out.println("Prime " + nodes[i].getValue());
        if (i > limit) {
            continue;
        }
    } else {
        continue;
    }
0
qo'shib qo'ydi