Удаление незначащих нулей из решета Эратосфена

@den18374 · Регистрация: 04.10.2013

Author24 — интернет-сервис помощи студентам

Я создал решето Эратосфена (решето простых чисел), но не могу сделать так, что бы в решете остались только простые числа без нулей. Сейчас программа выводит : 0 2 3 0 5 0 7 0 0 0 11 0 13... (где 0 - это бывшие составные числа). Помогите пожалуйста сделать так, чтобы Решето было без 0. Использование решета обязательно. Заранее большое спасибо!

Добавлено через 15 минут
вот моя программа на си:

C

#include <stdio.h>
#include <math.h>
main() {
        int i,j,q,f;
    int n,max;
    scanf("%d", &n);
    q=(sqrt(n)*30);
    int a[q];
 
 
        /*Создание Решета с 0(для составных чисел) и 1(для простых) */
    a[1]=0;
    for (i=2;i<=q;i++)
        a[i]=1;
    for (i=2;i*i<=q;i++) {
        if(a[i]==1) {
            for (j=i*i;j<=q;j+=i)
                a[j]=0;
        }
    }
 
 
 
 
    for (i=1;i<=q;i++) {
        if (a[i]==1)
            a[i]=i;
        }
        for (i=1;i<=q;i++)
                printf("%d", a[i]);
}

Day · 04.10.2013, 13:49

C

1	if (a[i]) printf("%d ", a[i]);

@den18374 · 04.10.2013, 14:26 **[ТС]**

Это само собой

Но мне нужно чтобы изначально в решете не было нулей, как избавиться от них в корне решета?

Day · 04.10.2013, 15:19

Простите, не понял вопроса

C

1 2	for(i=j=0; j<n; j++) if (a[j]) a[i++] = j+1;

Так пойдет?

@den18374 · 04.10.2013, 22:52 **[ТС]**

Не совсем; В общем идея задачи состоит в том чтобы с использованием решета Эратосфена найти наибольший простой делитель числа n, которое подается на вход, все бы ничего, но как только на вход программы идет число семи знаков или больше, программа вылетает с ошибкой. Так вот для того, чтобы этого избежать я использую число корень из n, чтобы избежать переполнения. только сейчас не могу понять как избавиться в самом решете от нулей, чтобы на их место поставить следующие простые числа.
Вот моя программа:

C

#include <stdio.h>
#include <math.h>
main() {
    int i,j,q,f,m,k,e;
    int n,max;
    scanf("%d", &n);
    q = (sqrt(n)+1);
    int a[n];
 
        /*Решето*/
    for (k=2;k <q;k++)
        a[k]=1;     
    for (k=2;k*k <n;k++) {
        if(a[k]==1){
            for (j=k*k;j <q ;j+=k) {
                a[j]=0;
            }
        }
    }
        /*_______________________*/
 
        /*Замена нулей и единиц на простые числа*/
        e=1;    
    for (k=2;k*k<n;k++)
    for (i=k*k; i<n; i+=k){
        if (a[i])
            a[e++]=i;
    }   
    
    /*_________________________________*/
        
 
 
        /*Поиск максимального простого числа*/
    f=0;
    for (i=2;i<=q;i++)
        if (n%i==0) 
            f=1;
    if (f==0) {
        printf("%d\n", n);
    }else{              
    for (i=1;i<=q;i++){
        if ((a[i]) && (n%a[i]==0) && a[i]>max)
            max=a[i]; 
    }
    printf("%d\n", max);
    }   
    return 0;
}

Добавлено через 4 минуты

Сообщение от Day

Простите, не понял вопроса

C

1 2	for(i=j=0; j<n; j++) if (a[j]) a[i++] = j+1;

Так пойдет?

Не совсем; В общем идея задачи состоит в том чтобы с использованием решета Эратосфена найти наибольший простой делитель числа n, которое подается на вход, все бы ничего, но как только на вход программы идет число семи знаков или больше, программа вылетает с ошибкой. Так вот для того, чтобы этого избежать я использую число корень из n, чтобы избежать переполнения. только сейчас не могу понять как избавиться в самом решете от нулей, чтобы на их место поставить следующие простые числа.
Вот моя программа:

C

#include <stdio.h>
#include <math.h>
main() {
    int i,j,q,f,m,k,e;
    int n,max;
    scanf("%d", &n);
    q = (sqrt(n)+1);
    int a[n];
 
        /*Решето*/
    for (k=2;k <q;k++)
        a[k]=1;     
    for (k=2;k*k <n;k++) {
        if(a[k]==1){
            for (j=k*k;j <q ;j+=k) {
                a[j]=0;
            }
        }
    }
        /*_______________________*/
 
        /*Замена нулей и единиц на простые числа*/
        e=1;    
    for (k=2;k*k<n;k++)
    for (i=k*k; i<n; i+=k){
        if (a[i])
            a[e++]=i;
    }   
    
    /*_________________________________*/
        
 
 
        /*Поиск максимального простого числа*/
    f=0;
    for (i=2;i<=q;i++)
        if (n%i==0) 
            f=1;
    if (f==0) {
        printf("%d\n", n);
    }else{              
    for (i=1;i<=q;i++){
        if ((a[i]) && (n%a[i]==0) && a[i]>max)
            max=a[i]; 
    }
    printf("%d\n", max);
    }   
    return 0;
}

Байт · 05.10.2013, 00:03

den18374, Могу дать совет. В качестве решета можно использовать байтовый массив. Один байт на 30 чисел. Дело в том, что из каждой тридцатки чисел только ВОСЕМЬ могут быть простыми (1, 7, 11, 13, 17, 19, 23, 29) (не считая первой тридцатки)
А в Байте помещается (вот удача!) ровно 8 битов (на себе проверял

) Экономия памяти - 32-х кратная.
Потому что

Сообщение от den18374

как только на вход программы идет число семи знаков или больше

очевидно - проблемы с памятью. Вот здесь

C

1 2	int a[n]; // или int a[q];

@den18374 · 05.10.2013, 00:33 **[ТС]**

Сообщение от Байт

den18374, Могу дать совет. В качестве решета можно использовать байтовый массив. Один байт на 30 чисел. Дело в том, что из каждой тридцатки чисел только ВОСЕМЬ могут быть простыми (1, 7, 11, 13, 17, 19, 23, 29) (не считая первой тридцатки)
А в Байте помещается (вот удача!) ровно 8 битов (на себе проверял

) Экономия памяти - 32-х кратная.
Потому что очевидно - проблемы с памятью. Вот здесь

C

1 2	int a[n]; // или int a[q];

Идею я понял, но к сожалению я еще не очень хорошо знаю Си

Расскажите пожалуйста как задать этот массив на Си,если, конечно, это не затруднит вас! Заранее спасибо!

Байт · 05.10.2013, 09:59

Вот набросок программки решета с использованием char-массива
Модифицируй ее под свои нужды.

C

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
static int Rest[8] = { 1, 7, 11, 13, 17, 19, 23, 29 };
static unsigned char *A;
static int V; // Объем массива A
#define N 12000  // До какого числа строить решето
main()
{ int s, p, ii, jj;
   V = N/30 + 1;
   A = (unsigned char *)malloc(V);
   A[0] = 1;
   memset(A+1, 0, V-1);
   s = sqrt(N);
   for(ii=p=0; p<=s; ii++) {
     for(jj=0; jj<8; jj++) {
       if (A[ii] &(1<<jj)) continue;
       p = 30*ii + Rest[jj]; // Простое
       Jolting(p);
     }
   }
   for(ii=0; ii<V; ii++) {
     for(jj=0; jj<8; jj++) {
       if (A[ii] & (1<<jj)) continue;
       printf ("%d\n", 30*ii + Rest[jj]);
     }
   }
 
}
/****************/
Jolting(int p)
{ int x, d, r, i;
 
   for(x=7*p; ; x += 2*p) {
     d = x/30;
     if (d >= V) break;
     r = x%30;
     for(i=0; i<8; i++) if (r==Rest[i]) break;
     if (i==8) continue;
     A[d] |= (1<<i);
   }
}
/****************/

Несколько первых простых пропущено, их можно добавить вручную Или немного
модифицировать алгоритм.
Функцию Jolting можно слегка оптимизировать, чего я делать не стал, тк. нас
в первую очередь интересует объем памяти.
Так же не стал заморачиваться на проблемах больших чисел и длинной арифметики.

@den18374 0 / 0 / 0 Регистрация: 04.10.2013 Сообщений: 6
	04.10.2013, 14:26 [ТС]	3
	Это само собой Но мне нужно чтобы изначально в решете не было нулей, как избавиться от них в корне решета? 0

	05.10.2013, 09:59