kazamuru

Muito obrigado pelo seu tempo e empenho em me explicar o algoritmo Arfneto, agora ficou mais claro. adicionado 2 minutos depois Entendi. Não precisa de um vetor adicional, por exemplo, tudo acontece no mesmo intervalo de endereços na memória. Muito bom o quicksort.

Olá Tenho uma duvida sobre o algoritmo Quick Sort, se puderem me ajudar, obrigado. Dentro da função quick_sort eu não entendi esse momento no qual os dois valores se encontram e a troca é realizada. Pelo que entendi, os dois "while" caminham em direção ao centro ate encontrarem um valor que seja maior e um valor que seja menor que o pivo. Nesse momento 'esq' e 'dir' param de se mover, pois encontraram as posições dos dois valores que podem ser trocados para os lados opostos. Se 'esq' e 'dir' param nessas posições do vetor, como é possivel que eles acabem se encontrando, no caso do if (esq<=dir) para que a troca aconteça? Qual o erro na minha lógica? PS: Não assumam que os comentários no código estejam corretos, foi o que eu entendi até agora olhando para esse algoritmo. #include<stdio.h> #define tam 10 void imprimeVetor(int vetor[tam]){ for(int i=0;i<tam;i++){ printf("|%d| ",vetor[i]); } } void quick_sort(int vetor[tam],int inicio,int fim){ int pivo,esq,dir,meio,aux; //limites da esquerda e direita da regiao analisada esq = inicio; dir = fim; //ajustando auxiliares do centro meio = (int) (esq + dir) / 2; //meio = posicao do meio do vetor pivo = vetor[meio]; //pivo = valor da posicao no meio do vetor while(dir > esq){ //percorre a metade esquerda (sentido ->) até encontrar um valor que seja MAIOR que o pivo, então PARA nessa posição. while(vetor[esq] < pivo){ esq = esq + 1; } //percorre a metade direita (sentido <-) até encontrar um valor que seja MENOR que o pivo, então PARA nessa posição. while(vetor[dir] > pivo){ dir = dir - 1; } //quando os limites se cruzam, realiza a troca dos valores nas posições encontradas anteriormente. if(esq <= dir){ //troca os valores dos lados do pivo aux = vetor[esq]; vetor[esq] = vetor[dir]; vetor[dir] = aux; //faz os limites laterais caminharem para o centro. esq = esq + 1; dir = dir - 1; } imprimeVetor(vetor); printf("\n"); } //AS RECURSÕES AGORA vão AJUSTAR AS METADES DIVIDIDAS PELO PIVO. //recursao caso 1: dir agora esta no centro (os limites se cruzaram antes) e vai ate o inicio. if(inicio < dir){ quick_sort(vetor,inicio,dir); } //recursao caso 2: esq agora esta no centro (os limites se cruzaram antes) e vai ate o fim. if(esq < fim){ quick_sort(vetor,esq,fim); } } int main(){ int vetor[tam] = {10,9,8,7,6,5,4,3,2,1}; imprimeVetor(vetor); printf("\n"); quick_sort(vetor,0,tam); //passo (vetor,inicio,fim) printf("\n"); return 0; }

Esse foi o código que resolveu mais rápido. São 4 minutos e 30 segundos no meu i5 3.3ghz: /*Faça um programa que calcule a soma de todos os números primos abaixo de dois milhões.*/ #include<stdio.h> int primo(int n){ int i; for(i=2;i<=n/2;i++){ if(n%i==0) return 0; } return 1; } int main(){ int i; unsigned long soma=0; int retorno; for(i=2;i<=2000000;i++){ retorno = primo(i); if(retorno==1){ soma+=i; } } printf("\nSoma: %lu",soma); return 0; Obrigado a todos pela ajuda!

@Flávio Pedroza Tentei. Está calculado bastante rápido e pelo que testei esta correto. Mas o calculo dos primos ate 1kk deu um numero negativo (levou uns 3 minutos) "-1104303640" adicionado 2 minutos depois @Leonardo0308 Vou tentar! De qualquer forma já melhorou muito!

@Leonardo0308 É verdade! Eu modifiquei a função que verifica se é primo: int primo(int n){ int div=0, i; for(i=1;i<=n;i++){ //divide cada um dos numeros passados por 1 ate 2.000.000 if(div==2) break; if(n%i==0) div++; //a cada divisao exata incremento 'div' } if(div==2){ //se houver apenas 2 divisores, entao é primo e retorno 1 arbitrariamente. return 1; } else return 0; } Fiz o calculo com 10.000 numeros e está muito mais rápido, obrigado. Será que ainda dá para melhorar isso? O calculo com 2kk ainda está muito demorado pelo que vi.

#include<stdio.h> //verifica se o numero eh primo. int primo(int n){ int div=0, i; for(i=1;i<=2000000;i++){ //divide cada um dos numeros passados por 1 ate 2.000.000 if(n%i==0) div++; //a cada divisao exata incremento 'div' } if(div==2){ //se houver apenas 2 divisores, entao é primo e retorno 1 arbitrariamente. return 1; } else return 0; } int main(){ int i; int soma=0; int retorno; for(i=1;i<=2000000;i++){ //passa os numeros de 1 a 2.000.000 para a função 'primo' retorno = primo(i); if(retorno==1){ //se for primo (retorno =1) é somado à variavel 'soma' soma+=i; } } printf("\nSoma: %d",soma); return 0;

O exercício pede : "Faça um programa que calcule a soma de todos os números primos abaixo de dois milhões." Eu fiz. Mas da forma que fiz está levando provavelmente bem mais de 1h para chegar ao resultado: c.txt Certamente existe um jeito muito melhor de fazer isso. Alguém pode me ajudar?