10 odpowiedzi w tym temacie

[bronstein]

Witam serdecznie, mam do napisania program wyświetlający liczby pierwsze z zadanego przedziału. Kod jaki sobie wymyśliłem to:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
main()
{
	  int i,x,y,j ;
		  printf("podaj x="); scanf("%d",&x);
		  printf("podaj y="); scanf("%d",&y);
	
	i=2;
	for(j=x;j<=y;j++)
	{while(j%i!=0)
	i++;
	if(i==j)
	printf("%d\n",j);
	i=2;}
			printf("\n");
			system ("PAUSE");
			return 0;
			}

problem w tym, że jak zacznę przedział od liczb mniejszych od 2 to nie działa...jak można to naprawić, może ewentualnie ktoś ma jakiś lepszy kod. Nie można używać tablic.

[Afroman]

[Ereinion]

Dla x = 1 to się powinno zapętlić w while'u tak na pierwszy rzut oka. Ale ogólnie to po co Ci w ogóle rozważać przedziały liczb mniejszych od 2 skoro tam nie ma liczb pierwszych? Daj przed for'em sprawdzenia czy: x <= y i y >= 2, jak to nie jest spełnione to od razu możesz zakończyć program, a jak jest to jeśli x < 2 to zacznij od x=2 i po kłopocie
No i  i = 2  ja bym dał przed while'm, zamiast w dwóch miejscach.

No i ogólnie są szybsze metody na znajdowanie liczb pierwszych, np wystarczy sprawdzać do

[bronstein]

Użytkownik Ereinion dnia 04.12.2011 - 22:12 napisał

Dla x = 1 to się powinno zapętlić w while'u tak na pierwszy rzut oka. Ale ogólnie to po co Ci w ogóle rozważać przedziały liczb mniejszych od 2 skoro tam nie ma liczb pierwszych? Daj przed for'em sprawdzenia czy: x <= y i y >= 2, jak to nie jest spełnione to od razu możesz zakończyć program, a jak jest to jeśli x < 2 to zacznij od x=2 i po kłopocie
No i  i = 2  ja bym dał przed while'm, zamiast w dwóch miejscach.

No i ogólnie są szybsze metody na znajdowanie liczb pierwszych, np wystarczy sprawdzać do

Chciałem dla mniejszych od 2 żeby program ładnie działał a nie stawał w miejscu:P A jak zacznę sprawdzać do   to co z resztą liczb pierwszych które znajdują się w zadanym przedziale? Nie bardzo to widzę ale poza tym dzięki za wskazówki.

[Ereinion]

No to jak zrobisz tak jak napisałem, to program będzie "ładnie działał" dla x < 2, bo on stawał w miejscu dla x=1, a przecież użytkownik, nie musi wiedzieć, że my szukanie tak czy siak zaczynamy od x=2

Trochę się źle wyraziłem, nie powinno być do tylko do , tzn dzielników x szukamy tylko wśród liczb od 2 do pierwiastka z x. Bo Ty szukasz od 2 do x, więc to trochę dłużej.

[Mariusz M]

#include<iostream>
#include<cstdlib>
 
using namespace std;
 
void sieve(int n);
 
int main(int argc,char** argv){
int n;
if(argc!=2) {
cout<<"Podaj argument"<<endl;
}
n=atoi(argv[1]);
sieve(n);
return 0;
}
 
 
void sieve(int n){
int i,j;
int* p;
p=new int[n+1];
for(i=0;i<=n;i++)
p[i]=0;
for(i=2;i<=n;i++){
for(j=i+i;j<=n;j+=i){
p[j]=1;
}
if(p[i]==0)
cout<<i<<" "<<endl;
}
delete[] p;
}

To jest sito Eratostenesa jednak ono wymaga użycia tablicy

Jak nie można używać tablic to sito odpada

Bez tablic

#include<iostream>
#include<cstdlib>
#include<cmath>

using namespace std;

int isprime(int n);

int main(int argc, char** argv){
int i,m,n;
m=atoi(argv[1]);
n=atoi(argv[2]);
for(i=m;i<=n;i++)
if(isprime(i))
cout<<i<<endl;
return 0;
}

int isprime(int n){
int b,i;
b=(n<2);
for(i=2;!(i>sqrt(n)||b==1);i++)
b=(b||(n%i==0));
return !b;
}

[matma4u]

Możesz również skorzystać z sita Atkina Bernsteina, które działa dużo szybciej niż sito Eratostenesa i wymaga mniej pamięci operacyjnej. Na tej stronie  znajdziesz informacje wraz z kodem:  http://edu.i-lo.tarn...search/0012.php

Autorem poniższego kodu jest: mgr Jerzy Wałaszek  - I Liceum Ogólnokształcące im. Kazimierza Brodzińskiego w Tarnowie -  http://edu.i-lo.tarnow.pl

// Sito Atkina-Bernsteina
// Data   : 21.03.2008
// (C)2008 mgr Jerzy Wałaszek
//----------------------------
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
  unsigned int n,g,x,y,xx,yy,z,i;
  bool * S;
  cin >> n;
  S = new bool[n+1];
  for(i = 5; i <= n; i++) S[i] = false;
  g = (unsigned int)(sqrt(n));
  for(x = 1; x <= g; x++)
  {
	xx = x * x;
	for(y = 1; y <= g; y++)
	{
	  yy = y * y;
	  z = (xx << 2) + yy;
	  if((z <= n) && ((z % 12 == 1) || (z % 12 == 5))) S[z] = !S[z];
	  z -= xx;
	  if((z <= n) && (z % 12 == 7)) S[z] = !S[z];
	  if(x > y)
	  {
		z -= yy << 1;
		if((z <= n) && (z % 12 == 11)) S[z] = !S[z];
	  }
	}
  }
  for(i = 5; i <= g; i++)
	if(S[i])
	{
	  xx = i * i;
	  z = xx;
	  while(z <= n)
	  {
		S[z] = false;
		z += xx;
	  }
	}
  cout << 2 << " " << 3 << " ";
  for(i = 5; i <= n; i++)
	if(S[i]) cout << i << " ";
  cout << endl;
  delete [] S;
  return 0;
}

[Xitami]

A czy na wspomnianej stronie wspomniano, że jest to prosta to znaczy naiwna implementacja?
Poprosiłem obu o policzenie ile jest liczb pierwszych mniejszych od 100 milionów, Atkin potrzebował 3.18 sekundy, a prosty Eratostenes 2,46.

[Xitami]

funkcję isprime() zaproponowaną przez Mariusza można napisać znacznie lepiej.

int isprime(int n){ int d;
		if( n<2 ) return 0;
		if( n%2==0 ) return n==2;
		if( n%3==0 ) return n==3;
		//if( n<5*5 ) return 1;
		for( d=5; d*d<=n; d+=6 )
				if( (n%d==0) || (n%(d+2)==0) )
						return 0;
		return 1; }

[Ereinion]

Być może czegoś nie dostrzegam, ale dlaczego powyższa implementacja jest "znacznie lepsza"? Wydaje się być jedynie bardziej czytelna, chociaż to pewnie kwestia gustu

[Xitami]

main(i,j){
		j=1;
		for( i=3; i < 2000000; i += 2)
				j += isprime(i);
		return ! printf("%d",j);}

Wersja Mariusza 3.99 sekundy, "moja" 1.18. Stosunek czasu 3.38
Zmniejszmy zakres z 2'000'000 do 1'245'000 oraz poziom optymalizacji, a czas Mariusza zostanie bez zmian, gdy mój to 0.64, czyli stosunek  6.23.
Kto to umieszcza pierwiastek w pętli?

[Mariusz M]

Pierwiastek mozna policzyc tylko raz w ciele funkcji sprawdzajacej czy liczba jest pierwsza i przechowac w jakiejs zmiennej lokalnej (wtedy wywolan pierwiastka bedzie troche mniej, tylko w funkcji glownej )  a u ciebie kwadrat moze wyjsc poza zakres typu int
Ostatecznie mozna podarowac sobie ten pierwiastek

Użytkownik Mariusz M edytował ten post 06.02.2012 - 07:05