How to set a one-dimensional array of primes in C only?
Closed due to the fact that the question is too general among participants Vladimir Martyanov , Yuri Negometyanov , Dmitriy Simushev , aleksandr barakin , fori1ton Mar 1 '16 at 15:01 .
Please correct the question so that it describes the specific problem with sufficient detail to determine the appropriate answer. Do not ask a few questions at once. See “How to ask a good question?” For clarification. If the question can be reformulated according to the rules set out in the certificate , edit it .
- oneDo you need to specify an array, or fill it with primes? Is this a learning task? - cy6erGn0m
- 3As the appearance of a woman, it immediately affects: what zeal everyone has to answer :) - cy6erGn0m
- one+1 just like here: hashcode.ru/questions/13334/… - yozh
- oneInterestingly, is “simple” a mathematical term here or is it a synonym for “integers”? =) - Alexey Sonkin
|
9 answers
To search for primes, use the Sieve Eratosthenen algorithm. Do not look at these strange examples.
Here is the code.
Arrays.fill(isPrime,true); isPrime[1] = false; for (int i=2; i*i < N; i++) if (isPrime[i]) for (int j=i*i; j < N; j+=i) isPrime[j] = false; Wrong a little - there in Java. But the meaning is the same.
Anton Feoktistov Anton Feoktistov
1.616 12 22
- And in order to get more prime numbers you can use sets implemented on bitmaps - GLAGOLA
- And this is generally a search for prime numbers of smaller N, and not a search for the first N prime numbers, which, I think, follows from the wording of the question. - avp 6:51 pm
- Exactly. But it works much faster. In any case, we need a one-dimensional array. The one-dimensional array has a length. - Anton Feoktistov
|
int limit = 1000; int sqr_lim; bool is_prime[1001]; int x2, y2; int i, j; int n; // Инициализация решета sqr_lim = (int)sqrt((long double)limit); for (i = 0; i <= limit; i++) is_prime[i] = false; is_prime[2] = true; is_prime[3] = true; // Предположительно простые - это целые с нечетным числом // представлений в данных квадратных формах. // x2 и y2 - это квадраты i и j (оптимизация). x2 = 0; for (i = 1; i <= sqr_lim; i++) { x2 += 2 * i - 1; y2 = 0; for (j = 1; j <= sqr_lim; j++) { y2 += 2 * j - 1; n = 4 * x2 + y2; if ((n <= limit) && (n % 12 == 1 || n % 12 == 5)) is_prime[n] = !is_prime[n]; // n = 3 * x2 + y2; n -= x2; // Оптимизация if ((n <= limit) && (n % 12 == 7)) is_prime[n] = !is_prime[n]; // n = 3 * x2 - y2; n -= 2 * y2; // Оптимизация if ((i > j) && (n <= limit) && (n % 12 == 11)) is_prime[n] = !is_prime[n]; } } // Отсеиваем кратные квадратам простых чисел в интервале [5, sqrt(limit)]. // (основной этап не может их отсеять) for (i = 5; i <= sqr_lim; i++) { if (is_prime[i]) { n = i * i; for (j = n; j <= limit; j += n) { is_prime[j] = false; } } } // Вывод списка простых чисел в консоль. printf("2, 3, 5"); for (i = 6; i <= limit; i++) { // добавлена проверка делимости на 3 и 5. В оригинальной версии алгоритма потребности в ней нет. if ((is_prime[i]) && (i % 3 != 0) && (i % 5 != 0)){ printf(", %d", i); } } Это один из алгоритмов нахождения простых чисел "Решето Аткина" 
johnfelix johnfelix
94 one eleven
- Explain how much memory you need to allocate under the is_prime array to search for, say, the first 10,000 prime numbers. - avp
|
Suppose that we are talking about the first N prime numbers. Put the first 3 {1, 2, 3} in the P [N] array. Recall that a prime number is odd, so we will go through only odd numbers. If the next candidate turns out to be simple, add it to the array and increase M - the current number of simple ones in the array (at the beginning, set M = 3).
Obviously, you need to experience numbers, starting with P [M-1] +2 (let's call it K). As a divisor we will take the primes already found, starting with P [2] (that is, triples). If the square of the next divisor (P [i] * P [i]) is greater than K, then K is a prime number, we put it in P, if we find out that K is composite, then we increase it by 2.
Repeat, until we type N primes.
For sufficiently large numbers, squaring will cause an overflow; this moment must be tracked and taken into account when determining the condition for the termination of the cycle for choosing the dividers. An effective solution to the head, something does not come, it is clear that this is K divided by something (in this case there will be extra tests of the candidate).
avp avp
37.4k 3 35 90
- @johnfelix, in his answer, gave a good solution to the problem of overflow in calculating the square. Indeed, this is solved through floating arithmetic. I wonder what will be the performance drop? - avp
|
void fill_primes(int* arr, size_t siz) { int prime = 2; while( siz-- ) { *arr++ = prime; prime = 5 - prime; } } 
VadimTukaev VadimTukaev
1,973 eight 14
- 3Formally, you are right. (Appreciated the joke). - avp
|
int main() { int f[1000]; int i, j; for (i = 2; i < 1000; i++) { for (j = 2; j <= (i / j); j++) if (!(i % j)) break; // если число имеет множитель, оно не простое if (j > (i / j)) cout << f[i] << "Простое число\n"; } return 0; } It seems so.
johnfelix johnfelix
94 one eleven
- And even for simplicity, why check? - avp
- Comrade AVP, go to the wiki and see ru.wikipedia.org/wiki/ Simple_number list, that all the prime numbers start from 2. I don’t say that here is an ideal algorithm, if you remove the array, then simple numbers are outputted, and with an array, you cant. - johnfelix
- And who would doubt that 1, 2 and 3 are simple? Just for them and apply the algorithm is not necessary. - avp
- @avp Could you name the date when the number
1was set simple? - alexlz - Not. I have always believed that a simple number is one that is completely divisible only by one and by itself. For 1, this rule is appropriate. And, looked at Vicky, well, according to science, this is not the case (this is what the Big Scientists mean. The correct classification of terms). - avp
|
NikiCh NikiCh
21 6
|
#include "stdafx.h" #include <iostream> #include <math.h> #include "windows.h" using namespace std; const int N=100; // размерность массива int mass[N]; // объявление массива int i,j, k; bool flag; int kon; int main() { k=0; for(i=2; k<=N; i++) { flag=false; for(j=2; j<i; j++) { if (i%j == 0) { flag=true; } } if(flag!=true) { mass[k]=i; k++; } } for(i=0; i<N; i++) cout<<mass[i]<<endl; cin>>kon; return 0; } NikiCh NikiCh
21 6
|
#include <iostream> #include <conio.h> using namespace std; int main() { int massiv[100]; for( int n=2, m=0;n<=100;n++,m++) { for( int i=2;i<=n; i++) { if(n%i==0 && n!=i) break; if(n%i==0 && n==i) { massiv[m]=n; cout<<massiv[m]<<" "; } } } _getch(); return 0; } 
Comfmore comfmore
484 6 13 25
|
Yes, here's another version of the work (using the Wilson theorem )
#include <stdio.h> const int N = 100; int main() { int simplenumbers[N]; int i, n, s; simplenumbers[0] = 2; simplenumbers[1] = 3; for(i=2, n=5, s=2; i<N; n+=s, s=6-s) { int j, fact; for(j=n-1, fact=1; j>1; j--) fact = (fact * j % n); if ((fact+1) == n ) simplenumbers[i++] = n; } for(i=0; i<N; i++) printf("%d ", simplenumbers[i]); putchar('\n'); } Why factorial is calculated modulo n , I think it is not necessary to explain.
UPD: added use of the rule that a prime number> 3 is 6k-1 or 6k + 1
alexlz alexlz
7,057 ten 12
|