не совсем простые числа

[pristizh]

Я бы не сказал что я новичок в этом деле, но и до уровня совсем одупляющегося програмиста я тоже пока не дорос. Учусь в 11 классе. к олимпиаде готовлюсь, работаю на паскале и только на паскале. Вот задача принцип решения я знаю, но всё дело в том, что она связана с большими числами и поэтому паскалю нехватает места даже если использовать longint, но может паскаль можно как-то обмануть? Вот суть задачи "
простых чисел бесконечно много но нас будут интересовать только те у которых цифры идут в порядки возрастания (например 17, 2347) таких чисел всего сто и последние сотое равно 23456789. Требуется написать программу, которая находит N-ое простое число с возрастающими цифрами" Помогите плис.



icq 408132450-если не понятно

[_-Re@l-_]

а, тип 123456789?Ну, чисто длинная арифметика.

[pristizh]

ну где ваши предложения друзья?

[LeBron]

Плоские алгоритмы поиска простых чисел, типа Эратосфена, не пройдут по времени.

Но раз чисел всего 100, и они в таких пределах... На реальных соревнованиях я бы просто написал прекалк, нашел тем же Эратосфеном все простых числа такого вида (в секунду вложить нереально, но даже самая примитивная реализация работает, очевидно, меньше минуты... и даже меньше полминуты), загнал константами, и получал бы ответ на запросы пользователя за О(1).

[pristizh]

Да нет, ты наверно не понял суть моего вопроса, решить её можно как угодно ( в частности с помощью Эратасфена) вопрос времени меня пока не интересует, дело в том что паскаль не считает большие числа к примеру если писать программу через Эратасфена то он найдёт сравнительно маленькие числа например 17,234 а к примеру а[96] он не выдаст, так как просто его не найдёт в связи со своей маленькой памятью.
Ну а перебором это просто не рационально и тупо.

[Serge_Bliznykov]

Вам же сразу в пост #2 дали ответ:
используйте длинную арифметику!

примеров полно (в том числе и на форуме)

[LeBron]

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

Да нет, ты наверно не понял суть моего вопроса, решить её можно как угодно ( в частности с помощью Эратасфена) вопрос времени меня пока не интересует, дело в том что паскаль не считает большие числа к примеру если писать программу через Эратасфена то он найдёт сравнительно маленькие числа например 17,234 а к примеру а[96] он не выдаст, так как просто его не найдёт в связи со своей маленькой памятью.
Ну а перебором это просто не рационально и тупо.

Сказано, что

таких чисел всего сто и последние сотое равно 23456789.

Если это так, то нам достаточно массив булей на 24 миллиона. Даже без битовых полей - это 24 мегабайта, с бит-полями получится 3 мб. Памяти хватает) А потом в осн.решении массив из 100 констант - тем более мало памяти)))
Числа совсем не большие, раз все цифры в возрастающем, то их не больше 9 (цифр), а это всегда в 4байтовом типе.

[pristizh]

нам достаточно массив булей на 24 миллиона




вы хотите сказать что я могу описать массив так допустим.
a: array[1..24000000]of boolea; ???????????????
Да фиг там, он компиляцию в этом месте не проходит, для него 24000000 слишком много, вот 24000 пропускает, но это для меня мало .......но у меня версия 7.0 стоит я не знаю какая у вас

[rrrFer]

в паскале же есть длинные целые числа, мне сейчас лень лезть за справочником. Но вот в С++ тип int до 32767 unsigned int 65535 число 23456789 действительно не входит
но есть ведь long int и там наибольшее число это 2147483647 вот тут нужное число уже легко входит, а есть ведь еще unsigned long int... ну на крайний случай можно и дробные числа использовать. Зачем вам массив на 24 миллиона элементов вообще не догнал.
а вот посмотрел: http://pascal.guti.ru/types.html

longint -2147483648..2147483647

чем вам не подходит?

#include <iostream>
#include <sstream>
using namespace std;
int main(){
	stringstream strstrm;
	char s[10];
	long int i,n,j,k;
	n=100;
	for(i=1,j=1;i<=23456789;i++){
		strstrm<<i;
		strstrm>>s;
		strstrm.clear();
		for(k=0;s[k+1];k++)
			if(s[k]>=s[k+1])
				break;
		if(!s[k+1]){
			for(k=2;k<i/2;k++)
				if(!(i%k))
					break;
			if(k>=i/2){
				cout<<i<<" #"<<j<<endl;
				j++;
				if(j>n)
					break;
			}
		}
	}
	cout<<"end"<<endl;
	cin.get();
	return 0;
}

вот на С++ программа, сделана очень лениво, прикреплен файл с результатом, кстати сотое число 1456789 а не 23456789.

как видно хватает массива из 10 элементов, куда вы хотите засунуть 24 миллиона элементов я даже не догадываюсь, поясните пожалуйста ))

[rrrFer]

а 23456789 это 105 число, соответствующее условию