Си: вывод простых чисел от 1 до N

Question

В первой строке содержится целое число ?. Нужно вывести все простые числа в диапазоне от 1 до ? включительно, по одному числу в строке.

Вот мой код, прога ничего не выводит и зависла по времени.
Посоветуйте, что сделать/исправить, пожалуйста.
P.S. Только начинаю изучать Си, поэтому простите мою тупость :)

#include<stdio.h>
int main(){
    int i, N, t, k;
    t=0;
    i=2;
    scanf("%d", &N);
    for (k=2; k<=N; k++){
        while(i<N){
            if (k%i==0){
                t++;
                i++;
            }
        if(t==0){
            printf("%d", k);
        }
        }
    }
}

Answer 1

#include<stdio.h>
int main(){
    int i, N, t, k;
   
    scanf("%d", &N);
    for (k=2; k<=N; k++){
        i = 2;
        t = 0;
        while(i < k){
            if (k%i==0){
                t++;
            }
            i++;
        }
        if(t==0){
            printf("%d\n", k);
        }
    }
}

Answer 2

Просто не вынесла душа такой неэффективности, как у Danis.

int main(int argc, const char * argv[])
{
    int N;
    scanf("%d",&N);
    if (N >= 2) puts("2");
    for(int n = 3; n <= N; n+=2)
    {
        int prime = 1;
        for(int i = 3; i*i <= n; i+=2)
            if (n%i==0) { prime = 0; break; }
        if (prime) printf("%d\n",n);
    }
}

А вообще этот вопрос уже столько раз обсасывался на RuSO, что не найти ответ - просто стыдно.

Просто ради интереса - для N = 100000 мой код работал на моей машине порядка 33 мс, код Danis для того же N - 17 секунд.

Answer 3

можно же гораздо короче:

#include <stdio.h>

int n=0;

int main()
{
    scanf("%d", &n);
    for(int b = 1;b <= n;b++)
    {
        printf("%d\n",b);
    }
    return 0;
}

Answer 4

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <stdbool.h>
 
int main ()
{
    int n, p;
    int *mass;
    bool flag; //"зачеркивали" ли число для данного p
    printf("Input n: ");
    scanf_s("%d", &n);
    if (n >= 2)
    {
        n = n - 1; //теперь n - это количество чисел в массиве
        mass = (int *)malloc(n * sizeof(int));
        for (int i = 0; i < n; i++)
            mass[i] = i + 2;
        for (int i = 0; i < n; i++)
        {
            p = mass[i];
            flag = false;
            for (int j = i + 1; j < n; j++)
            {
                if (!(mass[j] % p))
                {
                    for (int k = j; k < n - 1; k++)
                        mass[k] = mass[k+1];
                    flag = true;
                    n--; //уменьшаем, потому что чисел на одно стало меньше
                    j--; //уменьшаем, для того чтобы снова проверить на кратность j-е число. Оно же теперь стало другим
                }
            }
            if (flag == false) break;
        }
        for (int i = 0; i < n; i++)
            printf("%d ", mass[i]);
        free(mass);
    }
    else
        printf("Error. n must be >= 2\n");
 
    _getch();
    return 0;
}

Прошу прощения не учел увеличение множества, знакомый программист подсказал ответ взял отсюда

БЛОГ НА HUSL

Си: вывод простых чисел от 1 до N

Ответы (4 шт):