Как задать одномерный массив только из простых чисел в С?
-
1Вам надо задать массив, или заполнить его простыми числами? Это учебное задание?– cy6erGn0mCommented 29 июн. 2011 в 10:16
-
3Как появление женщины-то сразу влияет: какое рвение у всех ответить :)– cy6erGn0mCommented 29 июн. 2011 в 13:04
-
1+1 прям как здесь: hashcode.ru/questions/13334/…– yozhCommented 29 июн. 2011 в 17:47
-
1Интересно, а "простые" - это математический термин тут или же синоним "целые"? =)– Алексей СонькинCommented 30 июн. 2011 в 22:09
9 ответов
Для поиска простых чисел используйте алгоритм Решето Эратосфена. Не смотрите на эти странные примеры.
Вот тут есть код.
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;
Ошибся немного - там на яве. Но смысл тот же
-
А для того чтобы получить больше простых чисел можно использовать множества, реализованные на битовых массивах– GLAGOLACommented 29 июн. 2011 в 17:49
-
А это вообще поиск простых чисел меньших N, а не поиск первых N простых чисел, что как мне кажется, следует из формулировки вопроса.– avpCommented 29 июн. 2011 в 18:51
-
Именно так. Но работает гораздо быстрее. В любом случаи - нужен одномерный массив. У одномерного массива есть длина. Commented 29 июн. 2011 в 19:12
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);
}
}
Это один из алгоритмов нахождения простых чисел "Решето Аткина"
-
Объясните, сколько памяти надо выделить под массив is_prime для поиска, скажем, первых 10000 простых чисел.– avpCommented 30 июн. 2011 в 6:53
Допустим, что речь идет о первых N простых числах. Поместим в массив P[N] первые 3 {1, 2, 3}. Вспомним, что простое число нечетное, поэтому будем перебирать только нечетные. Если очередной кандидат окажется простым, добавим его в массив и увеличим M - текущее количество простых в массиве (в начале установим M=3).
Очевидно, что испытывать надо числа, начиная с P[M-1]+2 (назовем его K). В качестве делителя будем брать уже найденные простые числа, начиная с P[2] (т.е. тройки). Если квадрат очередного делителя (P[i]*P[i]) больше K, то K простое число, занесем его в P, если выяснили, что K составное, то увеличим его на 2.
Повторяем, пока не наберем N простых чисел.
Для достаточно больших чисел возведение в квадрат вызовет переполнение, этот момент надо отследить и учесть при определении условия прекращения цикла выбора делителей. Эффективное решение в голову, что-то не приходит, понятно, что это K, деленное на что-то (в таком случае будут лишние испытания кандидата).
-
@johnfelix в своем ответе привел хорошее решение проблемы переполнения при вычислении квадрата. Действительно, это решается через плавающую арифметику. Интересно, каково будет падение производительности ?– avpCommented 30 июн. 2011 в 6:48
void fill_primes(int* arr, size_t siz)
{
int prime = 2;
while( siz-- ) {
*arr++ = prime;
prime = 5 - prime;
}
}
-
3
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;
}
Кажется так.
-
-
Товарищь AVP зайдите на вики и посмотрите ru.wikipedia.org/wiki/Список_простых_чисел, что всетаки простые числа начинаются с 2. я не утверсждаю что здесь идеальный алгоритм если убрать массив то выводятся простые числа, а с массивом какойто косяк. Commented 30 июн. 2011 в 5:19
-
А кто бы сомневался, что 1, 2 и 3 простые? Просто для них и применять алгоритм не надо.– avpCommented 30 июн. 2011 в 6:42
-
@avp не могли бы Вы назвать дату, когда число
1
было назначено простым?– alexlzCommented 2 июл. 2011 в 3:47 -
Нет. Я всегда считал, что простым является число, которое без остатка делится только на единицу и само на себя. Для 1 это правило подходит. А, посмотрел Вики, ну по науке это не так (такова значит у Больших Ученых Правильная классификация терминов).– avpCommented 2 июл. 2011 в 10:07
#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;
}
#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;
}
Да вот ещё вариант работы (с использованием теоремы Вильсона):
#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');
}
Почему факториал вычисляется по модулю n
, думаю объяснять не надо.
UPD: добавлено использование правила, что простое число > 3 равно 6k-1 или 6k+1