Szukanie liczb pierwszych z przedziału <100;1000>

Question

Mam problem z zadaniem którego treść brzmi:

Napisz program, który wypisuje wszystkie liczby pierwsze z przedziału , w których występuje choć jedna cyfra 1 lub 3, ale ani razu nie występuje 2 lub 4. W momencie zakończenia pracy programu wszystkie liczby mają być widoczne na ekranie.

Tak jak z wszystkimi poprzednimi zadaniami sobie radziłem, tak to jest dla mnie czarną magią. Poniżej mam sito na liczby pierwsze, które MUSI BYĆ W TYM ZADANIU, jeśli ma być ono zaliczone(oczywiście trochę można w nim zmienić na rzecz rozwiązania zadania). Za wszystkie odpowiedzi i komentarze z góry bardzo dziękuje :D .

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <math.h>

using namespace std;

int main(){
	
int i,j, g, n;	

	
	int *tab = new int[n];
	
	for(i=0; i!=n; i++)
		{
			tab[i]=i;
		}
		
		g=floor(sqrt(n));
		
		printf("\n----granica = %d \n", g);
		
		for(i=2; i<g+1; i++)
			{
			if(tab[i]!=0)
					{
						j=i+i;
						while(j<=k)
						{
							tab[j]=0;
							j=j+i;
							}
						}
				}
	printf("\n Liczby piwerwsze to: ");
	for (i=2; i<=n; i++)
		{
			if(tab[i]!=0) printf("%d ", i);
			
			}
			printf("\n");
	return 0;
}

 

 

Comments

https://www.geeksforgeeks.org/sieve-eratosthenes-0n-time-complexity/

https://stackoverflow.com/questions/46803064/determine-if-a-number-contains-a-digit-for-class-assignment/46803249

Answer 1

Zamiast robić tablice intów, możesz zrobić tablice bool i wykreślać wszystkie liczby złożone. Następnie funkcje bool, która będzie sprawdzać czy w liczbie występuje 1 lub 3, a nie 2 i 4. 

#include <iostream>
#include <stdio.h>
using namespace std;

bool sprawdzanie_cyfr(int liczba)
{
    bool k=false;
    while(liczba!=0)
    {
        if((liczba%10==2)||(liczba%10==4))
        {
            return false;
        }
        else if((liczba%10==1)||(liczba%10==3))
        {
            k = true;
        }
        liczba/=10;
    }
    return k;
}

int main()
{
    bool sito[1000];

    for(int i=2;i<=1000;i++)
    {
        if(sito[i])
        {
            for(int j=i*i;j<=1000;j=j+i)
            {
                sito[j]=1;
            }
        }
    }

    for(int i=100;i<1000;i++)
    {
        if(sito[i]==0)
        {
            bool p_czy_f = sprawdzanie_cyfr(i);
            if(p_czy_f==true)
            {
                printf("%d ",i);
            }
        }
    }

    return 0;
}

 

Answer 2

Liczby pierwsze to te których nie ma w tabliczce mnożenia

Comments

A to co za śmieszna definicja? Liczby 2000 też nie ma w standardowej (szkolnej) tabliczce mnożenia, a jednak pierwsza nie jest.