102 lines
1.9 KiB
C
102 lines
1.9 KiB
C
/* Zad 1&2 z zestawu 2. Ćwiczenia z ASD.
|
|
* Wypisuje tablicę wskazującą liczby pierwsze ≤ 1024
|
|
* Następnie wypisuje liczby pierwsze Mersenne'a ≤ 2^20
|
|
* 23 sty 2019
|
|
* Michał Krzysztof Feiler (s444368) <archiet@wmi.amu.edu.pl>
|
|
* */
|
|
|
|
#include <math.h>
|
|
#include <stdio.h>
|
|
|
|
#pragma pack(push, 1)
|
|
|
|
#define N (1 << 10) - 1
|
|
|
|
struct bool_store {
|
|
int v : 1;
|
|
};
|
|
|
|
static struct bool_store _a[N - 1];
|
|
|
|
#pragma pack(pop)
|
|
|
|
int A_bf2_get(int i)
|
|
{
|
|
if (i < 2)
|
|
return 0;
|
|
return _a[i - 2].v;
|
|
}
|
|
|
|
void A_bf2_set(int i, int b)
|
|
{
|
|
_a[i - 2].v = b;
|
|
}
|
|
|
|
#define TRUE 1
|
|
#define FALSE 0
|
|
|
|
void doSE()
|
|
{
|
|
int i;
|
|
for (i = 2; i <= N; i++)
|
|
A_bf2_set(i, 1);
|
|
for (i = 2; i <= sqrt(N); i++)
|
|
if (A_bf2_get(i)) {
|
|
int j;
|
|
for (j = i * i; j <= N; j += i)
|
|
A_bf2_set(j, FALSE);
|
|
}
|
|
}
|
|
|
|
void do_and_print_mersenne()
|
|
{
|
|
int p, m, j;
|
|
for (p = 2; p <= 20; p++) {
|
|
if (!A_bf2_get(p))
|
|
continue;
|
|
m = (1 << p) - 1;
|
|
for (j = 2; j <= sqrt(m); j++)
|
|
if (m % j == 0)
|
|
continue;
|
|
printf(" 2 ^ %2d - 1 = %6d \n", p, m);
|
|
}
|
|
}
|
|
|
|
#define FILL_CHAR '-'
|
|
|
|
void do_and_print_eratostenes()
|
|
{
|
|
doSE();
|
|
int i;
|
|
for (i = 0; i <= N; i++) {
|
|
if (i % 10 == 0)
|
|
putchar('\n');
|
|
putchar(' ');
|
|
if (A_bf2_get(i))
|
|
printf("%4d", i);
|
|
else {
|
|
if (i >= 1000)
|
|
putchar(FILL_CHAR);
|
|
else
|
|
putchar(' ');
|
|
if (i >= 100)
|
|
putchar(FILL_CHAR);
|
|
else
|
|
putchar(' ');
|
|
if (i >= 10)
|
|
putchar(FILL_CHAR);
|
|
else
|
|
putchar(' ');
|
|
putchar(FILL_CHAR);
|
|
}
|
|
}
|
|
putchar('\n');
|
|
}
|
|
|
|
int main()
|
|
{
|
|
do_and_print_eratostenes();
|
|
do_and_print_mersenne();
|
|
return 0;
|
|
}
|