Liczby pierwsze z przedziału

Hej, treść zadania brzmi : Napisz program, który wypisze na ekran wszystkie liczby pierwsze z przedziału od 0 do 100.

Sęk w tym, że do napisania tego programu NIE WOLNO użyć żadnych wskaźników bądź też tablic. Wszystko na najbardziej podstawowych instrukcjach sterujących.

Wymyśliłem coś takiego : wprowadzam liczbę n do programu i dzielę ją kolejno w pętli przez liczby z przedziału (1..n) sprawdzając z każdym przebiegiem pętli reszte z dzielenia, jednocześnie zliczam ilość dzielników. Jeśli wyjdzie ilość liczników równa 2 to program wypisuje liczbe na ekran i inkrementuje pętlę zewnętrzną przechodząc do kolejnej liczby.

Program jednak nie działa jak trzeba, prosze o sugestie a nie gotowca :)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(void)
{
    int licznik = 0;
    int l = 2;
    for (l; l <= 100; l++)
    {
        for (int i = 1; i <= l; i++)
        {
            if (l % i == 0)
            {
                licznik = licznik + 1;
            }
        }
        if (licznik <= 2)
        {
            printf("%d\n", l);
        }
    }

    return 0;
}

Algorytm jest skrajnie niewydajny. Błędem jest niezerowanie zmiennej licznik.

Mała podpowiedź:

• dzielenie modulo 1 można sobie odpuścić
• żeby stwierdzić że liczba nie jest pierwsza wystarczy znaleźć jeden jej dzielnik
• powyżej i = sqrt(l) nie ma co szukać

Fakt algorytm nie jest najwydajniejszy ale niestety można korzystać tylko z najprostszych rozwiązań. Pomysł z szukaniem dzielnika tylko do pierwiastka danej liczby też jest niegłupi, spróbuję, a póki co problem jest rozwiązany, zapomniałem o zerowaniu dzielnika :) Proforma wklejam kod

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(void)
{
    int licznik = 0;
    int l = 2;
    for (l; l <= 100; l++)
    {
        for (int i = 1; i <= l; i++)
        {
            if (l % i == 0)
            {
                licznik = licznik + 1;
            }
        }
        if (licznik <= 2)
        {
            printf("%d\n", l);
        }
        licznik = 0;
    }

    return 0;
}

Taki kod

    for(int i=2;i<=sqrt(l);i++)
    {
        if(l%i==0)
        {
            licznik=licznik+1;
        }
    }
        if(licznik == 0)
       {
         printf("%d\n",l);
       }
       licznik=0;

też korzysta tylko z najprostszych rozwiązań, a jest znacznie wydajniejszy.

Zamiast

i<=sqrt(l)

można zrobić i*i<=l

Czarny Samiec napisał(a):

Zamiast

i<=sqrt(l)

można zrobić i*i<=l

Poza tym pętlę można przerwać gdy licznik zmieni wartość.

@Sopelek, @vpiotr, ten kod

long n = 1;
while((double)n*(double)n <= (double)Long.MAX_VALUE)
{
    if(!(n == (double)Math.sqrt(n*n)))
    {
        System.out.println(n + " nie jest równe");
    }            
    if(!(n <= Math.sqrt(n*n)))
    {
        System.out.println(n + " jest większe");
    }
    n++;
}

niczego na konsoli nie wyświetla. Zatem asekuracja jest chyba zbyteczna.

Skoro to tylko do 100, to w grę wchodzą tylko 4 pierwsze. A co za tym idzie

 
#include <iostream>

using namespace std;

int main()
{
    cout << "2\n3\n5\n7\n";
    for (int i = 4; i <= 100; i++)
    {
        if (i % 2 != 0 && i % 3 != 0 && i % 5 != 0 && i % 7 != 0) cout << i << "\n";
    }
    return 0;
}